Nieuws Scala28 oktober 2016

Trait what?

Trait linearization is the process in Scala that kicks in when you mixin traits in your class. The subject might look intimidating at first, but the process is actually quite simple. I expect that you already know what traits are and what you can do with them. This blog will focus on the trait linearization process.

Why do we need it?

In some languages there exists a way to inherit from multiple classes. In scala this is not possible, but it is possible to mixin multiple traits which feels a bit like multiple inheritance. Multiple inheritance can lead to the diamond problem(1). This is the problem where a class extends two other classes and implementations collide. As you can see in the diagram below, the inheritance looks like a diamond and both classes (TwoLegged and FourLegged) override the legs method. The question to solve is what the implementation of legs will be.

multiple-inheritance-2

Linearization

Scala linearization is a deterministic process that puts all traits in a linear inheritance hierarchy. By doing that we can solve the diamond problem, because we now know what the direct parent of the Beast class will be. Remember that the syntax to mixin traits is as follows: class A extends B with C with D. The rules for this process are as follows:

  1. Start at the first extended class or trait and write that complete hierarchy down. We will call this the linearized hierarchy
  2. Take the next trait and write this hierarchy down
    • now remove all classes/traits from this hierarchy which are already in the linearized hierarchy
    • add the remaining traits to the bottom of the linearized hierarchy to create the new linearized hierarchy
  3. repeat step 2 for every trait.
  4. Place the class itself as the last type extending the linearized hierarchy

Example

Let’s say the diagram above is coded like:


class Beast extends TwoLegged with FourLegged {
  override def legs = super.legs
}

Without the Linearization process it would be unclear where the super.legs resolves to. Because of the linearization process, the compiler determines that super points to FourLegged. Let’s write this down by applying the rules mentioned above:

  1. Start at the first extended class or trait and write that complete hierarchy down. The first trait is TwoLegged, so this leads to:
    TwoLegged -> AnyRef -> Any
  2. Take the next trait and write this hierarchy down. The next trait is FourLegged and the hierarchy is:
    FourLegged -> AnyRef -> Any

    • now remove all classes/traits from this hierarchy which are already in the linearized hierarchy. This removes AnyRef and Any, so we are left with:
      FourLegged
    • add the remaining traits to the bottom of the linearized hierarchy to create the new linearized hierarchy
      FourLegged -> TwoLegged -> AnyRef -> Any
  3. repeat step 2 for every trait. There are no more traits, so we are done.
  4. Place the class itself as the last type extending the linearized hierarchy
    Beast -> FourLegged -> TwoLegged -> AnyRef -> Any

The graphical representation looks like the picture below:

linearized-multiple-inheritance

This hierarchy clearly shows that calling super from Beast will resolve to the FourLegged trait and thus the value of legs will be 4.

Complex Example: order shuffling

In most cases the trait linearization process is straightforward. If you look at the hierarchy and then look at the order of trait mixin, there is a clear match in the order. Usually there is no need to play all the rules, just looking at the order of mixin is enough. Calling super from the class will point to the last trait that was mixed in. But be careful, this will not always be the case. Let’s look at a more complex example:

morecomplex

Let’s try to find out what the linearized hierarchy is for class D. As before we will apply the linearization rules one by one.

  1. Start at the first extended class or trait and write that complete hierarchy down. The first trait is FourLegged, so this leads to:
    FourLegged -> Base -> AnyRef -> Any
  2. Take the next trait and write this hierarchy down. The next trait is SixLegged and the hierarchy is:
    SixLegged -> TwoLegged -> Base -> AnyRef -> Any

    • now remove all classes/traits from this hierarchy which are already in the linearized hierarchy. This removes AnyRef and Any, so we are left with:
      SixLegged -> TwoLegged
    • add the remaining traits to the bottom of the linearized hierarchy to create the new linearized hierarchy
      SixLegged -> TwoLegged -> FourLegged -> Base -> AnyRef -> Any
  3. repeat step 2 for every trait. The next trait is TwoLegged and the hierarchy is:
    TwoLegged -> Base -> AnyRef -> Any

    • now remove all classes/traits from this hierarchy which are already in the linearized hierarchy. This removes AnyRef and Any, so we are left with:
      <<nothing>>
    • add the remaining traits to the bottom of the linearized hierarchy to create the new linearized hierarchy Because there is nothing to add it will stay the same:
      SixLegged -> TwoLegged -> FourLegged -> Base -> AnyRef -> Any
  4. repeat step 2 for every trait. There are no more traits, so we are done.
  5. Place the class itself as the last type extending the linearized hierarchy
    D -> SixLegged -> TwoLegged -> FourLegged -> Base -> AnyRef -> Any

We end up with the linearized structure as shown below. Now that we have this linearized structure we can answer what the first supertype of D is and we no longer have the diamond problem.

linearized-multiple-inheritance-1

Conclusion

The trait linearization might look intimidating at first, but as you have seen above, it consists of a few simple rules that you can apply yourself. It is good to be aware of this process. In daily life you don’t need to apply this rules that often. Also, placing println in the body of the traits that are mixed in will show you in what order the traits are executed and thus the hierarchy.