Linearization order in Scala

Question

I have difficulties in understanding the linearization order in Scala when working with traits:

class A {
  def foo() = "A"
}

trait B extends A {
  override def foo() = "B" + super.foo()
}

trait C extends B {
  override def foo() = "C" + super.foo()
}

trait D extends A {
  override def foo() = "D" + super.foo()
}

object LinearizationPlayground {
    def main(args: Array[String]) {

      var d = new A with D with C with B;
      println(d.foo) // CBDA????
  }    
}

It prints CBDA but I can't figure out why. How is the order of the traits determined?

Thx

Answer 1

An intuitive way to reason about linearisation is to refer to the construction order and to visualise the linear hierarchy.

You could think this way. The base class is constructed first; but before being able of constructing the base class, its superclasses/traits must be constructed first (this means construction starts at the top of the hierarchy). For each class in the hierarchy, mixed-in traits are constructed left-to-right because a trait on the right is added "later" and thus has the chance to "override" the previous traits. However, similarly to classes, in order to construct a trait, its base traits must be constructed first (obvious); and, quite reasonably, if a trait has already been constructed (anywhere in the hierarchy), it is not reconstructed again. Now, the construction order is the reverse of the linearisation. Think of "base" traits/classes as higher in the linear hierarchy, and traits lower in the hierarchy as closer to the class/object which is the subject of the linearisation. The linearisation affects how `super´ is resolved in a trait: it will resolve to the closest base trait (higher in the hierarchy).

Thus:

var d = new A with D with C with B;

Linearisation of A with D with C with B is

• (top of hierarchy) A (constructed first as base class)
• linearisation of D
  • A (not considered as A occurs before)
  • D (D extends A)
• linearisation of C
  • A (not considered as A occurs before)
  • B (B extends A)
  • C (C extends B)
• linearisation of B
  • A (not considered as A occurs before)
  • B (not considered as B occurs before)

So the linearization is: A-D-B-C. You could think of it as a linear hierarchy where A is the root (highest) and is constructed first, and C is the leaf (lowest) and constructed last. As C is constructed last, it means that may override "previous" members.

Given these intuitive rules, d.foo calls C.foo, which returns a "C" followed by super.foo() which is resolved on B (the trait on the left of B, i.e. higher/before, in the linearization), which returns a "B" followed by super.foo() which is resolved on D, which returns a "D" followed by super.foo() which is resolved on A, which finally returns "A". So you have "CBDA".

As another example, I prepared the following one:

class X { print("X") }
class A extends X { print("A") }
trait H { print("H") }
trait S extends H { print("S") }
trait R { print("R") }
trait T extends R with H { print("T") }
class B extends A with T with S { print("B") }

new B  // X A R H T S B     (the prints follow the construction order)

// Linearization is the reverse of the construction order.
// Note: the rightmost "H" wins (traits are not re-constructed)
// lin(B) = B >> lin(S) >> lin(T) >> lin(A)
//        = B >> (S >> H) >> (T >> H >> R) >> (A >> X)
//        = B >> S >> T >> H >> R >> A >> X

Answer 2

The accepted answer is wonderful, however, for the sake of simplification, I would like to do my best to describe it, in a different way. Hope can help some people.

When you encounter a linearization problem, the first step is to draw the hierarchy tree of the classes and traits. For this specific example, the hierarchy tree would be something like this:

The second step is to write down all the linearization of the traits and classes that interferes the target problem. You will need them all in the one before the last step. For this, you need to write just the path to reach the root. The Linearization of traits are as following:

L(A) = A
L(C) = C -> B -> A
L(B) = B -> A
L(D) = D -> A

The third step is to write the linearization of the problem. In this specific problem, we are planning to solve the linearization of

var d = new A with D with C with B;

Important note is that there is a rule by which it resolves method invocation by first using right-first, depth-first search. In another word, you should start writing the Linearization from most right side. It is as follow: L(B)>>L(C)>>L(D)>>L(A)

Fourth step is the most simple step. Just substitute each linearization from second step to third step. After substitution, you will have something like this:

B -> A -> C -> B -> A -> D -> A -> A

Last but not least, you should now remove all duplicated classes from left to right. The bold chars should be removed: B -> A -> C -> B -> A -> D -> A -> A

You see, you have the result: C -> B -> D -> A Therefore the answer is CBDA.

I know it is not individually deep conceptual description, but can help as an complementary for the conceptual description I guess.

---

And this part explains by relying on formula:

 Lin(new A with D with C with B) = {A, Lin(B), Lin(C), Lin(D)}
 Lin(new A with D with C with B) = {A, Lin(B), Lin(C), {D, Lin(A)}}
 Lin(new A with D with C with B) = {A, Lin(B), Lin(C), {D, A}}
 Lin(new A with D with C with B) = {A, Lin(B), {C, Lin(B)}, {D, A}}
 Lin(new A with D with C with B) = {A, Lin(B), {C, {B, Lin(A)}}, {D, A}}
 Lin(new A with D with C with B) = {A, Lin(B), {C, {B, A}}, {D, A}}
 Lin(new A with D with C with B) = {A, {B, A}, {C, {B, A}}, {D, A}}
 Lin(new A with D with C with B) = {C,B,D,A}

Answer 3

Scala's traits stack, so you can look at them by adding them one at a time:

1. Start with new A => foo = "A"
2. Stack with D => foo = "DA"
3. Stack with C which stacks with B => foo = "CBDA"
4. Stack with B does nothing because B is already stacked in C => foo = "CBDA"

Here's a blog post about how Scala solves the diamond inheritance problem.

Answer 4

The process by which scala resolve the super call is called Linearization In your example you create Object as

var d = new A with D with C with B;

So as specified scala reference docs Here call to super will be resolved as

l(A) = A >> l(B) >> l(c) >> l(D)

l(A) = A >> B >> l(A) >> l(C) >> l(D)

l(A) = A >> B >> A >> C >> l(B) >> l(D)

l(A) = A >> B >> A >> C >> B >> l(A) >> l(D)

l(A) = A >> B >> A >> C >> B >> A >> l(D)

l(A) = A >> B >> A >> C >> B >> A >> D >> l(A)

l(A) = A >> B >> A >> C >> B >> A >> D >> A

Now Start from left and remove duplicate construct in which right will be winning one

e.g. remove A and we get

l(A) = B >> C >> B >> D >> A

remove B and we get

l(A) = C >> B >> D >> A

Here we don't have any duplicate entry Now starting calling from C

C B D A

super.foo in class C will call foo in B and foo in B call foo in D and so on.

P.S. here l(A) is linearization of A

Answer 5

Well Actually I see you just reversed the Constructor linearization, which I think is pretty simple, so First let's understand constructor linearization

First Example

object Linearization3 {
  def main(args: Array[String]) {
    var x = new X
    println()
    println(x.foo)
  }
}

class A {
  print("A")

  def foo() = "A"
}

trait B extends A {
  print("B")

  override def foo() =   super.foo() + "B" // Hence I flipped yours to give exact output as constructor
}

trait C extends B {
  print("C")

  override def foo() =  super.foo() + "C"
}

trait D extends A {
  print("D")

  override def foo() =  super.foo() + "D"
}

class X extends A with D with C with B

Which outputs:

ADBC
ADBC

So to calculate the output I just take the class/traits one by one from left to right then recursively write outputs (without duplicates) here is how:

1. Our class signature is : class X extends A with D with C with B
2. So the first is A, since A has no parents (deadend) just print its constructor
3. Now D, which extends A, since we already printed A, then let's print D
4. Now C, which extends B, which extends A, so we skip A because it's already have been printed, we then print B , then print C (it's like a recursive funtion)
5. Now B, which extends A, we skip A, and we also skip B (nothing printed)
6. and you got ADBC !

Reversed Example (Your example)

object Linearization3 {
  def main(args: Array[String]) {
    var x = new X
    println()
    println(x.foo)
  }
}

class A {
  print("A")

  def foo() = "A"
}

trait B extends A {
  print("B")

  override def foo() = "B" + super.foo()
}

trait C extends B {
  print("C")

  override def foo() = "C" + super.foo()
}

trait D extends A {
  print("D")

  override def foo() = "D" + super.foo()
}

class X extends A with D with C with B

The Output is:

ADBC
CBDA

I hope that was simple enough for beginners like me

Answer 6

explanation, how the compiler sees a class Combined which extends the traits A with D with C with B

class Combined extends A with D with C with B {
  final <superaccessor> <artifact> def super$foo(): String = B$class.foo(Combined.this);
  override def foo(): String = C$class.foo(Combined.this);
  final <superaccessor> <artifact> def super$foo(): String = D$class.foo(Combined.this);
  final <superaccessor> <artifact> def super$foo(): String =  Combined.super.foo();
  def <init>(): Combined = {
    Combined.super.<init>();
    D$class./*D$class*/$init$(Combined.this);
    B$class./*B$class*/$init$(Combined.this);
    C$class./*C$class*/$init$(Combined.this);
    ()
  }
};

reduced example

You can read from left to right. Here is a small example. The three traits will print their name when initialized i.e. extended:

scala> trait A {println("A")}
scala> trait B {println("B")}
scala> trait C {println("C")}

scala> new A with B with C
  A
  B
  C
res0: A with B with C = $anon$1@5e025e70

scala> new A with C with B
 A
 C
 B
res1: A with C with B = $anon$1@2ed94a8b

So this is the basic linearization order. So the last one will overwrite the previous one.

Your problem is a little more complex. As you traits already extend other traits that themselves override some values of the previous traits. But the initialization order left to right or right will override left.

You have to keep in mind that the trait itself will be initialized first.

Answer 7

In addition to other anwsers you can find step-by-step explanation in snippet result below

hljs.initHighlightingOnLoad();

<script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.0.0/highlight.min.js"></script>
<link href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.0.0/styles/zenburn.min.css" rel="stylesheet" />
<link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" rel="stylesheet" />
<table class="table">
  <tr>
    <th>Expression</th>
    <th>type</th>
    <th><code>foo()</code> result</th>
  </tr>

  <tr>
    <td><pre><code class="scala"> new A </code></pre>
    </td>
    <td><pre><code class="scala"> A </code></pre>
    </td>
    <td><pre><code class="scala">"A"</code></pre>
    </td>
  </tr>

  <tr>
    <td><pre><code class="scala"> new A with D </code></pre>
    </td>
    <td><pre><code class="scala"> D </code></pre>
    </td>
    <td><pre><code class="scala">"DA"</code></pre>
    </td>
  </tr>
  
    <tr>
    <td><pre><code class="scala"> new A with D with C </code></pre>
    </td>
    <td><pre><code class="scala"> D with C </code></pre>
    </td>
    <td><pre><code class="scala">"CBDA"</code></pre>
    </td>
  </tr>
  
   <tr>
    <td><pre><code class="scala"> new A with D with C with B </code></pre>
    </td>
    <td><pre><code class="scala"> D with C </code></pre>
    </td>
    <td><pre><code class="scala">"CBDA"</code></pre>
    </td>
  </tr>
</table>