Trait vs inheritance; dispatch time

I am not happy with my understanding of traits.

I get that for arguments vs inheritance, people often point out:
() "has-a" vs "is-a"
(
) diamond problem

Something else I am currently trying to understand is "dispatch", this notion taht with inheritance, much of dispatch happens at runtime, vs traits where as much of "dispatch" happens at compile time.

Can someone elaborate on this (if the claim is even true at all) ?

This is not an answer to the question, but does provide a way of differentiating traits from inheritance.

Inheritance implement a cascade: we inherit from our ancestors (and no one else). We can add things to what we inherit, which our descendants (but no one else) will inherit from us.

Traits implement a matrix: each thing (row) can be assigned whatever traits (columns) we wish. There is no ancestry or forced inheritance; hence we do not inherit the defects or unwanted behavior of our ancestors.

2 Likes

I want to 'steel man' rather than 'straw man' this argument -- and I admit I am not sure I understand what you are saying. However, K am not convinced taht "directed acyclic graph" vs "matrix" is the key distinction.

It seems that in a language like C++/Java, one can simulate the 'matrix' setup by simply saying:

do not inherit from classes that have members

so now, at this point, one can have a 'matrix' where
columns = Java/C++ class/structs,
rows = interfaces / abstract classes with no members

However, that seems different from Rust's trait system.

Perhaps I am misunderstanding something, but I do nots ee 'dag' vs 'matrix' as the defining difference.

Regarding dispatch, you can use static or runtime dispatch with either approach. In C++ you get runtime dispatch for virtual methods as I recall (haven't done much C++ recently). With rust you get runtime dispatch by using dyn Trait. The decision of which you get is placed differently in the code (class definition versus type use) but three kind of dispatch isn't really a strongly distinguishing feature.

3 Likes

Yeah, my premise is definitely off. I'm now also convinced that 'dispatch' is certainly not a defining characteristic.

With class inheritance their are obviously ancestors and descendants (whatever the specific language calls them). That's the chain of class inheritance. There are no such relationships with traits; any object can be given any set of traits that are meaningful to it. If you've never read the Second Rust koan, it's worth some contemplation.

Incidentally, I was part of the original Honeywell Green team whose language design for the US DoD is now known as Ada, so I'm quite familar with the Strawman Ironman Steelman progression.

1 Like

My understanding of Rust Koans​​​​​ is that it actually has nothing to do with traits vs inheritance, but everything to do with "do you have to list all traits/superclasses at time of defining a struct" ?

For example:

  1. https://en.wikipedia.org/wiki/Common_Lisp_Object_System definitely has a class hierarchy. I'm pretty sure the problem can be solved in CLOS.

  2. Even in plain Java, one can do "class BrotherFarbold implements interface CookingDuties"

==

My understanding of that koan is that it makes two assumptions:

  1. with traits, you can add new traits later on

  2. with inheritance, you haver to define everything in inherit from up front when the class is defined

==

I am not sure I agree with (2).

Furthermore, if we look at smalltalk, I think we would agree that (1) the language is definitely inheritance based (2) it is possible to add new message handlers at runtime.

So one could definitely add a "cookdinner:" message handler to class BrotherFarbold and solve the task that way.

Again, I do not know enough about traits to state defining characteristic of trait vs inheritance, but it seems that particular koan, the issue is "can we add functions / message handlers to a struct after it has been defined" rather than "trait vs inheritance"

The fact that Java supports features that are not inheritance does not make those features a version of inheritance.

Would the following fall under 'inheritance'

abstract class CookDinner{  
  abstract void cook_dinner();  
}  
class BrotherFarbold extends CookDinner{
  ...
}  

Let`s start by dispatch. In some OO terminology, objects encapsulate state and only communicate to each other via messages. Using that terminology, it becomes more easy to grasp what "dispatch" is: sending the message to the right destination. Polymorphism essentially means different objects responding in different ways to the same message.
The message is what we most commonly call "invoking a method". So dispatching is about what happens when you invoke a method. In the case of static dispatching the recipient of the message is resolved during compilation. That means that the next execution point will be hard-wired already in compilation time.
In dynamic dispatching when you reach a certain execution point where you invoke the method, it will be resolved at runtime which execution path to take next. That is definitely more flexibly, but it does not take much analysis to understand this cannot be implemented as efficiently as static dispatching.
Language comparison:

  • C++ : static dispatch is used by default. By defining a method as virtual, you enable dynamic dispatching. Still only applicable if you call objects via a pointer, or reference.
  • Java: dynamic dispatching
  • Rust: at client code side you need to mark as dyn to use dynamic dispatch (I like this - very explicit when you want to use it or not)
  • Smalltalk: never wrote a line on it, but I always read it also natively has double dispatching (dispatching depends on the types of both communicating objects). This is achieved in other languages by the visitor pattern.

Not quite. As described above, you can opt-in to have dynamic dispatch with traits. Also, the contrast you make only makes sense if the language support both types of dispatching. So I will stick to comparing Rust to C++ here. C++ inheritance you do not automatically move into dynamic dispatching - only virtual methods do.
With inheritance what you get is:

  • Run time polymorphism , if you apply dynamic dispatching
  • Access to protected attributes and methods
  • Storage of the attributes - so memory use inheritance is also a mechanism to extend the data you store
    (this last point is what leads to diamond hierarchy problems)

In Rust does not have protected attributed/methods, and you get no attributes/memory storage from implementing a Trait.

Over the years C++ programmers turned more frequently from runtime polymorphism, achieved via inheritance to compile-time polymorphism achieved with templates (generics), for being more efficient. In C++20 this finally has reached a new level with Concepts, which look a bit similar to Traits. But still, you need to decide whether you want to model something as Concept and work solely with compile-time polymorphism or as class and work solely with run-time polymorphism. In Rust Traits I liked that you get compile-time polymorphism by default, but you can opt-in to run-time polymorphism should you need the flexibility attached to runtime resolution.

So I see a Trait as something you can choose to use either as a Java Interface or a C++20 Concept depending on the context. I like it :smiley:

8 Likes

It's important to note that traits cannot always be turned into trait objects (dyn <trait>). The subset of traits, that can be turned into trait objects are referred to as object-safe. Therefore, dynamic dispatch is not even always a matter of choice. Luckily, the rules about what is considered object-safe allow us to work around that in many cases.

(the following section is copied from the Rust reference)


Object Safety

Object safe traits can be the base trait of a trait object. A trait is object safe if it has the following qualities (defined in RFC 255):

  • It must not require Self: Sized
  • All associated functions must either have a where Self: Sized bound, or
    • Not have any type parameters (although lifetime parameters are allowed), and
    • Be a method that does not use Self except in the type of the receiver.
  • It must not have any associated constants.
  • All supertraits must also be object safe.

When there isn't a Self: Sized bound on a method, the type of a method receiver must be one of the following types:


Random Thoughts

I kinda wish Rust offered a way to annotate a trait directly, that asserts object safety and communicates the intent to provide object safety clearly. This would be especially handy when dealing with super traits. When super traits get involved, asserting object safety becomes non-trivial, because every super trait also has to be object-safe for the base trait to remain object-safe.

I generally dislike the design philosophy of having object safety be a "happy accident", that can turn into an unhappy incident when adding new methods (with default implementation) to the trait. IMO, it should be like const, an explicit guarantee from the library author to the library user.

5 Likes

That's intriguing. I'm new here, and it occurred to me just a couple days ago that the interface I'm working on could use dyn <trait>, and as luck would have it that went quite smoothly (I guess the constraints mentioned above aren't all that narrow anyway.)

But it didn't occur to me at the time to think about the dynamic dispatch that this apparently depends on. Since the trait in question never needed any annotation or anything that prepares it to be used in this way, I guess any object that can be a "trait object", is physically a trait object with the necessary run time "vtable[s]" in case they're needed?

By the way, what I'm doing is an interface to C++ library, and dyn <trait> helps model the automatic base cast we have in C++. If we're looking for semantic distinctions between inheritance and traits, maybe it would be interesting to look at collisions. I've been thinking about C++ collision because my interface is prone to erroneously pick up a base class implementation of a non-virtual member function if I'm not careful. For virtual functions, I understand that the subclass overwrites the base class vtable, so one may count on getting the subclass function though the object has been cast to its base; two base classes with the same function will lead to a compiler error. I don't right off hand see any way to encounter this ambiguity with dynamic traits.

Unlike C++, which stores the vtable pointer inside the structure data, Rust keeps track of the vtable in the compiler until an &dyn Trait object is created. At that point, the vtable pointer is stored as the second slot of a fat pointer. This has a couple of advantages:

  • The cost of dynamic dispatch, including extra memory usage for the vtable pointer, is borne entirely by code that uses dyn Trait objects
  • Dynamic dispatch is available for types that need a specific memory layout, such as FFI types.
3 Likes

My three cents:

Dispatch determines the process of choosing the right functions out of multiple functions, sometimes also known as overload resolution.
Although Rust doesn't count itself as a language supporting overloading you still can overload functions but only those located in traits.

Dispatching can be determined statically because the type having a has-a relationship with the trait is
known at compile time, e.g. a struct.
Dispatching can be determined dynamically because the type having a has-a relationship with the trait is known at run time, e.g. an Animal might be a Dog or Cat or something else can only be investigated at run time.

Some points:

  • Although it is easy to differentiate these two in Rust, it is not in other languages as you can dispatch the same type dynamically (you try to unbox the underlying type) or you use the boxed type shadowing the underlying type for dispatching, then you statically dispatch
  • Languages able to run code at compile time (CTFE) may encounter dynamic dispatching at compile time, a more correct term for differentiation would be deterministic (static code analysis) vs nondeterministic dispatch (dynamic code analysis, by running it)

As you might notice value:Type means the value value conforms to the type Type with an is-A relationship (although in Rust the : operator is sometimes used to express subtype relationships in generic constraints).
The same is also true for Traits when treating them as types.
Imagine a trait as a set containing those values which associate to/(has) the functions listed by the trait definition. When this is true, these functions can be called with the dot operator like: value.function.

Comparing to Java, a value conforms to an interface only if it contains these functions as part of its own definition which is somewhat more restricted. Contains relationships are seen as is-A relationships.

Indeed, I agree that the current design is a bit suboptimal.

Luckily, defining a macro that asserts object safety is easy. There is one available at ::static_assertions (one that may break on edition 2021, though, due to its lack of dyn).

You can even write one that allows you to decorate the trait definition itself:

#[macro_rules_attribute(assert_object_safe!)]
trait Default {
    fn default () -> Self; // Error, use of `Self` breaks object safety
}

The other direction, however, is harder: if you don't want to accidentally be object-safe, the shortest way is to add a Sized bound on the trait. But this prevents you from implementing your trait for slices and other trait objects, which may be unfortunate.

Luckily, adding an associated const currently does the trick.

trait NotObjectSafe {
    const __NOT_OBJECT_SAFE: () = {};

    /* ... */
}
  • (which can thus be macro-ed too).

  • Or you could just define a dummy trait that is not object safe, and use it as a super trait when needed:

    pub
    trait NotObjectSafe {
        const __: () = { impl<T : ?Sized> NotObjectSafe for T {} };
    }
    
    trait Foo : NotObjectSafe {
        /* ... */
    }
    
2 Likes