Order of method call in Scala trait mixin

Question

I have a program structured as:

abstract class IntQueue {
 def get(): Int
 def put(x: Int)
}
trait Doubling extends IntQueue{
 abstract override def put(x: Int) {
   println("In Doubling's put")
   super.put(2*x)
 }
}
trait Incrementing extends IntQueue {
 abstract override def put(x: Int) {
  println("In Incrementing's put")
  super.put(x + 1)
 }
}
class BasicIntQueue extends IntQueue {
 private val buf = new ArrayBuffer[Int]
  def get() = buf.remove(0)
  def put(x: Int) {
   println("In BasicIntQueue's put")
   buf += x
 }
}

When I do:

val incrThendoublingQueue = new BasicIntQueue with Doubling with 
                                            Incrementing
incrThendoublingQueue.put(10)
println(incrThendoublingQueue.get())

Output is:

In Incrementing's put

In Doubling's put

In BasicIntQueue's put

22

I am a bit confused about ordering here. My understanding of linearization order for this scenario is:

BasicIntQueue -> Incrementing -> Doubling -> IntQueue -> AnyRef -> Any

So when I call put, shouldn't BasicIntQueue's version be called first?

Answer 1

No. The linearization in this case is

{<anonymous-local>, Incrementing, Doubling, BasicIntQueue, IntQueue, AnyRef, Any}

The BasicIntQueue serves a the base of the mixin stack, with Doubling wrapping around it, and then Incrementing wrapping around both Basic and Doubling. So, when you call put on the entire thing, the outermost Incrementing is hit first, then the Doubling, then finally the Basic. The Basic must come last, because ultimately, it cannot delegate the actual insertion of the elements into the buffer to anyone else.

You can:

1. Just read the spec and convince yourself that it must be the case
2. Implement a toy-version of the algorithm from the spec, see what it outputs for various class definitions (it's somewhat enlightening, but mostly done for fun)

---

Reading the spec

The section 5.1.2 of the Spec tells you precisely how the linearization is computed. You seem to have forgotten to reverse the indices 1 ... n in L(c_n) + ... + L(c_1).

If you apply the correct formula, you get the following linearizations for the involved traits and base classes:

     IntQueue : {IntQueue, AnyRef, Any}
     Doubling : {Doubling, IntQueue, AnyRef, Any}
 Incrementing : {Incrementing, IntQueue, AnyRef, Any}
BasicIntQueue : {BasicIntQueue, IntQueue, AnyRef, Any}

If you then finally combine these linearizations to compute the linearization of the anonymous local class that is instantiated as incrThendoublingQueue:

<anonymous-local-class>, L(Incrementing) + L(Doubling) + L(BasicInt)

you obtain the linearization already shown above. Therefore, the methods should be invoked in this order:

• incrementing
• doubling
• basic

which is consistent with the actual output.

---

Reimplementing linearization algorithm for fun

This is actually one of those dependency-free snippets of the specification that you can implement easily from scratch. The definition of concatenation with replacement can be copied from the spec as-is, it's almost runnable code (except that the funny plus with arrow is somewhat difficult to type, and that I wanted it as an infix operator on lists):

implicit class ConcatenationWithReplacementOps[A](list: List[A]) {
  def +^->(other: List[A]): List[A] = list match {
    case Nil => other
    case h :: t => 
      if (other contains h) (t +^-> other)
      else h :: (t +^-> other)
  }
}

Modeling a class declaration C extends C1 with ... with Cn is also really simple:

case class ClassDecl(c: String, extendsTemplate: List[ClassDecl]) {
  def linearization: List[String] = c :: (
    extendsTemplate
      .reverse
      .map(_.linearization)
      .foldLeft(List.empty[String])(_ +^-> _)
  )
}

The formula for linearization is implemented as a method here. Notice the reverse.

The example given in the spec:

val any = ClassDecl("Any", Nil)
val anyRef = ClassDecl("AnyRef", List(any))
val absIterator = ClassDecl("AbsIterator", List(anyRef))
val richIterator = ClassDecl("RichIterator", List(absIterator))
val stringIterator = ClassDecl("StringIterator", List(absIterator))
val iter = ClassDecl("Iter", List(stringIterator, richIterator))

println(iter.linearization.mkString("{", ", ", "}"))

produces the output exactly as in the spec:

{Iter, RichIterator, StringIterator, AbsIterator, AnyRef, Any}

Now, here is a model of your example:

val intQueue = ClassDecl("IntQueue", List(anyRef))
val doubling = ClassDecl("Doubling", List(intQueue))
val incrementing = ClassDecl("Incrementing", List(intQueue))
val basicQueue = ClassDecl("BasicIntQueue", List(intQueue))

val incrThendoublingQueue = ClassDecl(
  "<anonymous-local>", 
  List(basicQueue, doubling, incrementing)
)

println(incrThendoublingQueue.linearization.mkString("{", ", ", "}"))    

It produces the linearization order that I've already shown above:

{<anonymous-local>, Incrementing, Doubling, BasicIntQueue, IntQueue, AnyRef, Any}

Everything seems to work as expected, no reason to write to Scala-Users.

Answer 2

The ordering of the output reflects the actual linearization, which is

Incrementing -> Doubling -> BasicIntQueue -> IntQueue -> AnyRef -> Any

Explanation

A class declaration

class C extends S with T1 with T2

is linearized to

C -> T2 -> T1 -> S

The traits come before the class S because the traits can modify the behaviour of S and must therefore be lower in the class hierarchy. Likewise a later trait can modify an earlier trait and must therefore be lower in the class hierarchy. Hence the order of the classes and traits in the linearization is the reverse of the declaration order.

Your example

Applying this to your example, the line

val incrThendoublingQueue = new BasicIntQueue with Doubling with Incrementing

is roughly the same as

class Temp extends BasicIntQueue with Doubling with Incrementing
val incrThendoublingQueue = new Temp()

Using the transformation above, Temp is linearized to

Temp -> Incrementing -> Doubling -> BasicIntQueue

This gives the class hierarchy that is implied by the output of your code.