2.4. Rust and ad-hoc polymorphism using traits

In this chapter we will dive deeper into the Rust type system and look at how interface-like behavior is realized in Rust through traits. Once we know about traits, we can also write powerful generic code using type constraints. At the end of this chapter you will know how to write your own traits and use them in generic code, and how to use the different traits for creating and converting types that the Rust standard library offers.

A deeper look at type conversions

In the previous chapter we talked about type conversions and saw that Rust doesn't do any implicit (i.e. automatic) conversions between types for us. We used this fact to build an abstraction for non-zero integers to constrain the domain of functions on the integers. In this chapter, we will improve the ergonomicsA common term used by programmers that translates to "How much code do I have to write/repeat when using this thing?" of the NonZeroI32 type. Before reading on, first take a look at our current implementation of NonZeroI32 and a usage example, and answer the following question for yourself:

mod safety {
    pub struct NonZeroI32(i32);

    impl NonZeroI32 {
        pub fn inner(&self) -> i32 {
            self.0
        }
    }

    // Other code omitted...
}

fn div(a: i32, b: safety::NonZeroI32) -> i32 {
    a / b.inner()
}

Let's tackle some of these shortcomings, starting with the problem of accessing the inner i32 value. Currently we have the inner() function, which is a more verbose way of simply doing b.0 in the function body of div. We can think of inner() as another type conversion, from NonZeroI32 to i32Technically from &NonZeroI23 to i32, but we'll talk about references (&) later. To make our thinking a bit easier, it makes sense to use a different syntax when we talk about function definitions. Instead of describing our function in natural language ("A conversion from type A to type B") or in full Rust code (fn inner(&self) -> i32), we can take inspiration from the mathematical notation that we saw in the previous chapter. Recall this definition of the mathematical function for integer division:

\[ f : \mathbb{Z} \times (\mathbb{Z} \setminus {0}) \to \mathbb{Z}, \quad f(x, y) = \lfloor \frac{x}{y} \rfloor \]

The first part describes only the types that are involved, without giving them any names or anything. We can do the same thing in Rust and describe only the input and output types of a function:

fn(NonZeroI32) -> i32

// For brevity, we will omit the `fn()` part:
NonZeroI32 -> i32

Definition: This special syntax is called the function signature. Multiple functions with different names can have the same signature if they have the same set of input argument types and output type. This will become useful later on when we talk about passing around functions to other functions!

An interesting property of the function signature syntax is that every function signature describes a total function:

Definition: A function \(f\) from domain \(S \subseteq X\) to codomain \(Y\) is called total if \(S = X\). In natural language: "\(f\) is a total function if it is defined for every element of \(X\)"

Going from a NonZeroI32 value to the inner i32 value always works, because every possible NonZeroI32 has a valid inner i32. What about the opposite direction?

i32 -> NonZeroI32

This is obviously not a total function, as we do not want to allow to go from 0 to a NonZeroI32 value! Functions that are only defined on a subset of the input domain are called partial functions. Most programming languages do not have a way to express partial functions at the type level and instead fall back to runtime checks. This is exactly what we did when we used the panic! functionTechnically panic! is not a function but a macro: We deferred something that we could not express through types (i.e. at compile-time) to a runtime check. For a dynamically-typed language such as Python, almost all type checks are performed at runtime, which is why we see fast iteration cycles in Python, but typically a lot more runtime errors than e.g. in Rust.

Rust does provide a way to express partial functions, but you will have to wait a bit longer until we will cover that topic. If patience is not your strong suite, check out the section on Enums and Pattern Matching from the Rust book.

For now, let's stick with the conversion from NonZeroI32 to i32, for which we wrote a custom inner() function. It turns out that such one-to-one conversions (from type A to type B) are a very common pattern in Rust. The language still does not do conversions automatically, but the Rust standard library has defined a common interface for type conversions. You might recall from chapter 2.2 that Rust is not an object-oriented language, so talking about interfaces in Rust might confuse you. We use the term interface a bit more informally to mean "A way to define a common set of behavior". The technical term for interfaces in Rust is traits, and we will look at them now!

Traits - Defining common behavior in Rust

Before continuing with this section, you are encouraged to read the chapter on Traits in the Rust book. It talks about the idea behind traits and gives a bunch of examples on how to use them.

To not lose sight of the problem, we are looking for a way to either simplify or standardize the type conversion NonZeroI32 -> i32 and maybe also the reverse direction i32 -> NonZeroI32 (with the runtime panic! if we pass in 0). You might notice some symmetry while looking at these type signatures:

i32 -> NonZeroI32
NonZeroI32 -> i32

The first line is a conversion from the i32 type into the NonZeroI32 type, while the second line is a conversion from the NonZeroI32 type into the i32 type. We could just as well swap the "from" and "into" in the first statement: A conversion into the i32 type from the NonZeroI32 type. We might write it like this, by flipping the arrow:

i32 <- NonZeroI32

This is not a valid type signature, but it illustrates the symmetry of type conversions. This gives us two ways of implementing type conversions: One from the perspective of the source type, and one from the perspective of the target type. Our safety::make_non_zero function from the previous chapter was written from the perspective of the target type NonZeroI32. This is hard to see since we wrote it as a free-standing function, but we could also have implemented it as a function on the type NonZeroI32:

impl NonZeroI32 {
    pub fn from_i32(val: i32) -> Self { // "Self" is the same type as "NonZeroI32", it's a shorthand notation when inside an `impl` block
        // Implementation is the same as before
    }
}

// Call it like so:
div(2, safety::NonZeroI32::from_i32(1));

We could also have written this conversion from the perspective of the source type i32, however we can't do so using an impl i32 block, as the Rust visibility rules prevent us from implementing new functions on what is called a foreign type, i.e. a type that we did not define within our own code. But let us assume for now that we couldWe actually can, using a small workaround that is considered idiomatic Rust. Stay tuned!, in which case the conversion would look like this:

impl i32 {
    pub fn as_non_zero(&self) -> safety::NonZeroI32 {
        safety::NonZeroI32::from_i32(self)
    }
}

It might seem redundant to write the code in this way, as it simply defers to the code we wrote previously from the perspective of the target type. However if we could write the code in this way, it would allow us to call the non_zero_i32 function on the i32 type! You might not have seen such syntax from other programming languages, typically primitive types don't have methods that you can call on them, but in Rust this is allowed and looks like this:

div(2, 1.as_non_zero());

That is a significant improvement in ergonomics! Unfortunately we can't write the implementation of as_non_zero on the i32 type. What we learned however is that we can (in theory) improve ergonomics of type conversions by making use of the symmetry inherent to the type conversions. B::from(a) is the same thing as a.to_b()! This is a general pattern, and as programmers we love patterns, as they are ways to prevent us from repeating ourselves! So let's look for a way to exploit this pattern to make arbitrary type conversions easier to write!

First, we need a way to state that a type A converts to another type B. An interface for type conversions, if you will. We use the trait keyword to define an interface-like type in Rust. We will also take our learning from the previous example and instead of defining a ToB trait, use the inverse FromA notation. We will see in a second why this is a good idea:

trait FromA {
    fn from(value: A) -> Self; // Self refers to the type that we will implement this trait ON
}

We could then implement this trait on any type B that we want to convert from an A:

impl FromA for NonZeroI32 {
    fn from(value: A) -> NonZeroI32 { // Could have written "-> Self", but "-> NonZeroI32" makes it clearer what the `from` function returns!
        // TODO Figure out how `A` converts to `NonZeroI32`...
    }
}

// Call like this:
let a: A = ...; // Get an `A` from somewhere
let v = NonZeroI32::from(a);

We used a placeholder name A, but that doesn't make much sense, after all what exactly is A? What we really mean is "any type", for which the corresponding language feature is called generics, as we already saw in chapter 2.2. This is the same feature that makes it possible to write a std::vector<T> class in C++ that works for any type T: std::vector<int>, std::vector<std::string>, std::vector<std::vector<int>> etc. So let's adjust our trait to take any type AYou might be used to the letter T when seeing generic code. There is nothing special about T, it doesn't even have to be a single letter. std::vector<AnyType> would have been possible as well. T is a shorthand for "type", it is simple to write, so it became a default. In our case, we talked about abstract types A and B, so we stick with A now.:

trait From<A> {
    fn from(value: A) -> Self;
}

Now, we can implement this trait for any type we want:

impl From<i32> for NonZeroI32 {
    fn from(value: i32) -> NonZeroI32 {
        if value == 0 {
            panic!("Can't create NonZeroI32 from 0");
        }
        NonZeroI32(value)
    }
}

It is also possible to implement the same trait on the same type with a different generic argument:

impl From<i16> for NonZeroI32 {
    fn from(value: i16) -> NonZeroI32 {
        Self::from(value as i32)
    }
}

Here we used the language-feature of explicit type casts between primitive types using the as keyword to delegate to the From<i32> implementation! Now we can convert from i32 and i16 values to NonZeroI32!

We are now ready to implement a bit of magic, by looking at the opposite direction of the type conversion. We have B::from(a) but what we really want is a.into() to make a B. The signature of into() is A -> B, just as the signature of from() is A -> B, but the difference is that from() is a function on the type B, whereas we want into() to be a function on a value of A. Functions on values are often called member functions and they are all the functions that take a first argument named self in RustOr any of the variants: &self, &mut self. self is very similar to this in other languages.

Comparison: Functions on types in Rust are the same thing as static member functions in C++. Functions on values (called instances) of a type in Rust are the same thing as non-static member functions in C++. Only if you have an instance of a type do you get access to this/self, which points to that exact instance.

Let's define another trait:

trait Into<B> {
    fn into(self) -> B;
}

Now traits can be implemented on foreign types, even on primitive types, so we are allowed to do this:

impl Into<NonZeroI32> for i32 {
    fn into(self) -> NonZeroI32 {
        NonZeroI32::from(self)
    }
}

impl Into<NonZeroI32> for i16 {
    fn into(self) -> NonZeroI32 {
        NonZeroI32::from(self)
    }
}

But notice the code duplication: We had to implement Into<NonZeroI32> on both the i32 and the i16 types separately, even though the function body looks the same in both cases. We know that we can implement Into<NonZeroI32> on all types T if NonZeroI32 implements From<T>. Rust lets us implement traits on generic types as well, which is a very powerful feature:

impl<T> Into<NonZeroI32> for T {
    fn into(self) -> NonZeroI32 {
        NonZeroI32::from(self)
    }
}

This does not yet compile, as the compiler can't guarantee that there is actually a function NonZeroI32::from(T) that returns a NonZeroI32! There are obvious examples where such a function does not (yet) exist, for example the f32 type, for which we haven't implemented From<f32> on NonZeroI32. So we have to add a type constraint that says "Only those types where NonZeroI32 implements From<T>". This is how it looks like:

impl<T> Into<NonZeroI32> for T where NonZeroI32: From<T> {
    fn into(self) -> NonZeroI32 {
        NonZeroI32::from(self)
    }
}

Now we get the ergonomics we want:

div(2, 0.into());

If you try to compile this code, you might notice that it doesn't work because the Rust compiler complains about multiple defined names. As it turns out, the From/Into traits are so useful that the Rust standard library provides these exact traits and Rust auto-imports them into every Rust file you write! To learn more about From and Into, you can look at the corresponding section in "Rust By Example". One thing that is worth looking at is the way Into is implemented for any type that itself implements FromThis is called a blanket implementation, as it covers all types like a blanket:

impl<T, U> Into<U> for T    // For all ordered pairs of types (`T`, `U`) implement the `Into<U>` trait
where                       // But only those pairs where type `U` implements the `From<T>` trait
    U: From<T>,
{
    fn into(self) -> U {    // Implementation of the `into` function that creates a `U` value from a `T` value (`self` has type `T`)
        U::from(self)       // Defer to the `from` function of the `From<T>` trait! 
    }
}

What this blanket implementation does is it allows us to implement a conversion just once (using impl From<OtherType> for OurType) and gives us the .into() function on OtherType for free!

impl<T> From<T> for T {
    fn from(t: T) -> T {
        t
    }
}

Standard traits for creating and converting types

These conversion traits can be found in the std::convert module of the Rust standard library. If you skim the documentation, you will see a bunch of explanations that we have not yet covered:

• Both From and Into only handle value-to-value conversions. To understand what that means we have to learn what a value in Rust is and how it differs from references. Then we can understand the two additional traits AsRef and AsMut, which deal with reference conversions. References are covered in chapter 3.3
• Conversions might fail, so Rust provides TryFrom and TryInto as fallible versions of From and Into. We will learn about how to represent computations that can fail in chapter 5

For now, let's look at one other trait that is easier to understand with our current level of knowledge: Default. While we previously talked about conversions, this trait is all about creating values. It serves a similar purpose to the default constructor in C++, in that it lets us create a value of a type from "thin air". Just as in C++ we can have only one default constructor for a type, we can only have one implementation of Default for a type. In fact, any specific trait can only be implemented at most once for any typeYou might have noticed in the previous section that we implemented From twice on the NonZeroI32 type. This is different though, since one implementation was of From<i32> and the other of From<i16>. The way the Rust type system works, these are two distinct traits, which makes it legal to implement both on the NonZeroI32 type.. If we choose to implement Default, this is the Rust way of stating "This is how to default-construct a value of this type".

trait Default {
    fn default() -> Self;
}

The Default trait provides one single method default with the following signature: () -> Self. Unpacking this signature is insightful:

• This function takes zero arguments, as it creates a default instance out of thin air. In C++ we would have written "zero arguments" as void, the corresponding Rust type is called the unit type and is written as (). Perhaps a bit confusingly, () is a type name and also the only valid value of that type. So creating an instance of () is written as ()
• The Self keyword denotes a specific kind of type that is only meaningful within an impl block. In the signature within the Default trait it can be read as "Whatever the type of the current implementor of this trait is"

To illustrate the second statement, let's implement Default for a new type:

struct NewStruct(i32);

impl Default for NewStruct {
    fn default() -> Self { 
        // "Self" and "NewStruct" are the same type within this impl block!
        NewStruct(42)
    }
}

Default has two functions: First, it gives a common way of writing and calling a default constructor on a type. In our previous example, we could then call NewStruct::default() to obtain a default instance of NewStructNote that even though this gives us a default instance, it doesn't guarantee that every value returned from calling default() is actually the same. Take a UUID as an example: We do want every new UUID to be different, so UUID::default() returning a different value every time it is called actually makes sense.. The second feature is that it can be a useful generic type constraint, if we are in a generic function (or generic type) that requires creating instances of the generic type. A simple but contrived example would be to define a global function that creates a default instance of any type:

fn construct<T: Default>() -> T { // "<T: Default>" is equivalent to writing "where T: Default" after the return type. 
    T::default()
}

// Equivalent syntax:
fn construct<T>() -> T 
    where T: Default {
    T::default()
}

Just as in the blanket implementation of Into, this function defers to the Default trait and its default() function. This works because the type constraint T: Default tells the compiler that the Default trait must be implemented for whatever type we call construct with. If this is guaranteed the compiler will then know how to find the implementation of Default and the corresponding default() function.

Traits vs. interfaces in other languages

Traits are a special way of providing interface-like functionality in a programming language. Since interfaces are about standardizing shared behavior on types, you might be used to object-oriented concepts such as inheritance and virtual functions to realize interfaces. C++ certainly handles them like that, though it doesn't have a dedicated interface keyword (compared to Java for example). A limitation of virtual functions is that they only let you write shared functionality for member functions. There are no virtual static functions in C++Though we can achieve similar behaviour through function pointers! In Rust, we are allowed to define non-member functions on traits: Default does that, as does the From trait. If you are interested in programming language history, the inspiration behind traits in Rust are type classes in Haskell. On the technical side, both interfaces using virtual functions as well as traits are forms of polymorphismA term borrowed from biology, based on the greek term polymorphos, meaning "of many forms".

Definition: Polymorphism in programming languages refers to strategies for using the same symbol to represent multiple different types.

There are three main approaches to polymorphism in use by programming languages today:

1. Ad-hoc polymorphism
2. Parametric polymorphism
3. Subtyping

For an in-depth explanation of these approaches, the paper "On understanding types, data abstraction, and polymorphism." by Cardelli and Wegner {{#cite cardelli1985understanding}} is a worthwhile read. We will stick to a concise overview focused at explaining the difference between Rust traits and interfaces in other programming languages.

Ad-hoc polymorphism is best understood through operator overloading:

std::cout << 42 << "," << 42.0;

In this C++ example, operator<< is (ab-)usedIt is debatable whether using the symbol << for stream insertion was a good choice, as it does clash with its usage as the bit-shift operator: 2 << 8 to pipe data into stdout. The same symbol (<<) has different meaning and executes different code, depending on the type argument(s) that it is called with. This is made possible through operator overloading in C++ and is a form of polymorphism. It is ad-hoc because all different overloads must be known statically (i.e. at compile-time). If the corresponding header files containing the implementation of operator<< for int and const char* are not included, this code will not compile.

Rust traits work in the same way as operator overloading (they are a form of ad-hoc polymorphism): If we write code like let val: NonNegativeI32 = 2.into():, the call to into() is semantically equivalent to Into::<NonNegativeI32>::into(0). Since we can call into() on many different types, the into() function is effectively overloaded based on the type we call it on. Just as with operator overloading, calling trait functions on a type only works if the compiler can see the impl block of the trait for that type. Therefore, the set of all existing implementations of the trait is always known at compile-time, which is why ad-hoc polymorphism is sometimes called closed polymorphism.

#![allow(unused)]
fn main() {
let val: NonNegativeI32 = 2.into();
}

std::string val = std::make_unique<std::string>();
// Compilation of the next line fails with "couldn't deduce template parameter '_Tp'"
// std::string val = std::make_unique();

#![allow(unused)]
fn main() {
fn foo(v: NonNegativeI32) {}

foo(2.into()); // Compiles and `into()` is deduced as `Into::<NonNegativeI32>::into()`
}

Subtyping works quite differently and usually defers the resolution of which function to call on a type to some runtime data structure. The canonical Java example listed on the Wikipedia page for Polymorphism explains it very succinctly:

abstract class Pet {
    abstract String speak();
}

class Cat extends Pet {
    String speak() {
        return "Meow!";
    }
}

class Dog extends Pet {
    String speak() {
        return "Woof!";
    }
}

static void letsHear(final Pet pet) {
    println(pet.speak());
}

static void main(String[] args) {
    letsHear(new Cat());
    letsHear(new Dog());
}

A function letsHear take instances of type Pet or any subtype of that type. Whereas in ad-hoc polymorphism, different functions were executed through the same symbol, implementation of letsHear is the same for Cat and Dog. What is different is the implementation of speak for these types, which is only resolved at runtime through a virtual table (vtable for short): A data structure containing a function pointer for each virtual function in the base type. This process of looking up the correct function based on the type at runtime is called late binding.

Compared to ad-hoc polymorphism, late binding is what enables subtyping to work with unknown types at compile-time. New subtypes of Pet can be written by anyone even after the code for letsHear was compiled. This is impossible with ad-hoc polymorphism. The downside of late binding is that is happens at runtime and thus has a runtime cost, compared to ad-hoc polymorphism which is resolved entirely at compile-time.

But what if we still want to use Rust traits and let other code add new types that implement the trait? This is where parametric polymorphism comes into play. Instead of writing code with concrete types, we make the type of a function argument or member variable a parameter. The corresponding language feature is often called generic code. We already saw generic code in Rust in the definition of the From and Into traits:

trait From<A> {
    fn from(value: A) -> Self;
}

The function from takes a single argument of a parametric type, which can be read as "This function takes any type". Since traits themselves are also a form of polymorphism, it can get confusing to distinguish the two, so let's look at a generic function that is not associated with a trait instead:

fn equals<T>(l: T, r: T) -> bool {
    l == r
}

This function takes two arguments of the same type T, but what T is exactly is undefined. It is not any specific type but instead a placeholder where a specific type will be filled in at some point. Just like with subtyping, this function has the same implementation for every possible type. It does however defer to another function (the == operator), which will be implemented differently depending on the specific type that will be filled in for T. We'll get to that in a moment. First, let's look at what happens if this code is called:

equals(2, 3);

When the compiler encounters this expression, it has to find the correct function equals to call with the given arguments. Integer literals have the default type i32 in Rust, so the compiler will look for a function called equals that takes two arguments of type i32The return type is ignored for now, and never plays a role in function resolution as Rust functions are uniquely determined by their name and argument types, not by the return type. Rust also does not support function overloading, so each fully qualified name of a function (with module paths) must be unique. Two functions with the same name but different arguments are not allowed.. It does find the generic function fn equals<T>(l: T, r: T) -> bool, which is a potential candidate. This function is polymorphic, which gives two possible ways of generating the actual machine code for this call: Either keep equals as a polymorphic function and perform late binding, or turn it into a non-polymorphic function that can be resolved at compile-time. Rust chooses the latter path and will turn the polymorphic equals<T> function into a specific equals<i32> function in a process called monomorphization: Going from a many-shaped function to a function with a single shape. At this point the compiler will generate a so-called instantiation of the equals function by replacing the parametric type T with i32. In doing so, it has to check if the resulting code is valid, which requires checking if the expression l == r is valid if l and r are of type i32.

At least this is what C++ would do if you were using templates. Rust generics work a bit different: Even though the equals function is parametric over an arbitrary type T, every usage of that type implies some capabilities. The Rust language requires that these capabilities are stated explicitly as generic bounds on the type parameter(s). In our case, we have one capability: The existence of an overload of the == operator for type T. Luckily, operators are only syntactic sugar in Rust, every operator is provided by a specific trait. The == operator is provided by the PartialEq trait. We already saw how to add constraints to generic types, stating "This type must implement this specific trait", so we can fix our equals code:

fn equals<T: PartialEq>(l: T, r: T) -> bool {
    l == r
}

Monomorphization turns this generic function into the following function:

fn equals(l: i32, r: i32) -> bool {
    l == r
}

Since there is an impl PartialEq for i32 block somewhere in the Rust standard library, the type constraint i32: PartialEq is met and i32 is a valid type for usage with the generic equals function. Notice that after monomorphization, ad-hoc polymorphism kicks in to find the correct overload of the == operator (i.e. the correct implementation of the PartialEq trait) for the type i32.

Observation: While Rust does allow unconstrained type parameters, as soon as we try to use such a type, we have to introduce type constraints so that the compiler can guarantee that the usage pattern is valid. The only way to constrain a type in Rust is by specifying which traits the type must implement. Therefore, parametric polymorphism and ad-hoc polymorphism always go hand in hand in Rust.

It is worth to compare the previous code example with an equivalent example written in a C++ version prior to C++20 (which introduced concepts, a similar feature to Rust traits):

template<typename T>
bool equals(T l, T r) {
    return l == r;
}

C++ templates work through something called duck typing, which means the compiler will look for functions that look like the usage pattern we need. In this case, an operator== that takes two parameters of the same type and returns something that is convertible to bool. This has several downsides:

1. The usage patterns are not obvious. Since C++ allows implicit conversions, this might find an operator== that takes arguments of some other type U, given that there is a non-explicit conversion from T to U implemented somewhere. In more complex examples, there might also be hidden usage patterns in the code that are not desired, such as the existence of specific constructors or conversion operators.
2. Since the type requirements are never explicitly stated, this can lead to confusing compilation errors if a template function is called with invalid arguments. Whereas in the Rust example, a compilation error would state "the trait PartialEq is not implemented for Type" if called with a Type that doesn't implement PartialEq, a C++ compiler will instead complain about a missing overload of operator==. With such a small example, the difference in error messages might not seem big, but experienced C++ programmers know that this can quickly get out of hand for heavily templated code.

To defend C++, with C++20 concepts were introduced as a language feature, which allow generic type constraints in a very similar way to traits in Rust:

#include <concepts>

template<typename T>
requires std::equality_comparable<T>
bool equals(T l, T r) {
    return l == r;
}

Recap

In this chapter we learned what traits are in Rust, and how they can be used to defined shared behavior of types as well as to make generic code possible. We saw the idiomatic ways of converting between types and creating default instances of types. We also learned about the concept of polymorphism and three different ways that it is typically realized in a programmnig language.

Closing exercises

fn max_element<T: Ord>(a: T, b: T, c: T) -> T {
    if a >= b && a >= c {
        a
    } else if b >= a && b >= c {
        b
    } else {
        c
    }

    // Or as a one-liner using the provided `max` method from the `Ord` trait:
    // a.max(b.max(c))
}

use std::fmt::Display;

fn foo_generic<T: Display>(val: T) {
    println!("The value is: {val}");
}

fn main() {
    foo_generic(42);
    foo_generic("42");
    foo_generic(false);
}