Scala: Dynamic Dispatch

Consider this Scala code:

class X {
    def m(a:A) = a.f(this) + ", " + "m(a:A) in X"
}

class Y extends X {
    override def m(a:A) = a.f(this) + ", " + "m(a:A) in Y"
}

class Z extends Y

class A {
    def f(x:X):String = "f(x:X) in A"
    def f(y:Y):String = "f(y:Y) in A"
}

class B extends A {
    override def f(x:X):String = "f(x:X) in B"
    def f(z:Z):String = "f(z:Z) in B"
    def g(x:X):String = super.f(x) + ", " + "g(x:X) in B"
    def h(y:Y):String = B.g(y) + ", " + "h(y:Y) in B"
}

object B {
    def f(x:X) = "f(x:X) in ObjB"
    def g(y:Y) = f(y) + ", " + "g(y:Y) in ObjB"
    def g(z:Z) = f(z) + ", " + "g(z:Z) in ObjB"
}

class C extends B {
    override def f(y:Y):String = "f(y:Y) in C"
    def h(z:Z):String = super.h(z) + ", " + "h(z:Z) in C"
    def k(x:X):String = x.m(this) + ", " + "k(x:X) in C"
}

The question given is: Give the output of running the following program:

val z: Z = new Z; val x: X = new Y
val c: C = new C; val a: A = new B
println(a.f(x)); println(a.f(z))
println(c.g(z)); println(c.h(z))
println(c.k(x))

I cannot seem to fully understand the output given. Here's what I think happens:

println(a.f(x)) = "f(x:X) in B"
println(a.f(z)) = "f(z:Z) in B"
println(c.g(z)) = "f(y:Y) in A, g(x:X) in B"
println(c.h(z)) = "f(y:Y) in A, g(y:Y) in ObjB, h(y:Y) in B, h(z:Z) in C"
println(c.k(x)) = "f(y:Y) in C, m(a:A) in Y, k(x:X) in C"

Yet, when I actually put the code into REPL, I get a different result:

println(a.f(x)) = "f(x:X) in B"
println(a.f(z)) = "f(y:Y) in A"
println(c.g(z)) = "f(x:X) in A, g(x:X) in B"
println(c.h(z)) = "f(x:X) in ObjB, g(y:Y) in ObjB, h(y:Y) in B, h(z:Z) in C"
println(c.k(x)) = "f(y:Y) in C, m(a:A) in Y, k(x:X) in C"

Why is this? I know that it is something to do with how overloaded methods are selected, but I could not find a single resource that precisely specifies how to determine which methods are selected, and when. If someone could explain the exact process, I would be grateful.

Solution

I don't think this has anything to do with linearization as there is no multiple inheritance in the example. This example is about dispatch with methods overriding and overloading.

First we need to separate "actual type" and "declared type". For examlpe in

val x: X = new Y

for variable x declare type is X and actual type is Y. You can't change actual type of a value but you can assign value of some actual type to variables of different declared types if they are super-types.

There is one simple (and a bit simplified) rule for call dispatch: for method overloading, which is dispatched first, i.e. when an object is passed as a parameter, its declared type is used to select the method; for method overriding i.e. when a method is called on an object, its actual type is used to select the method.

Additional rule this has always declared type of the class in which it is declared.

Also you should learn how to debug your applications. Debugging will easily show you which methods are called.

Types

val x: X = new Y
val z: Z = new Z; 
val a: A = new B
val c: C = new C;

x has declared type of X and actual type Y
z has both declared and actual types of Z
a has declared type of A and actual type B
c has both declared and actual types of C

Example #1 is trivial, so I'll omit it.

println(a.f(z)) = "f(y:Y) in A"

Here we first need to resolve overloading i.e. find in type A method that accepts type closest to Z. It is

def f(y:Y):String = "f(y:Y) in A"

Now we need to dispatch overriding i.e. check if B overrides this method and the answer is no, there is no override for that method in B so output is generated by the method in A.

The reason why B's

def f(z:Z):String = "f(z:Z) in B"

is not selected is that a has declared type of A and thus B's more specific method is not visible in this context.

println(c.g(z)) = "f(x:X) in A, g(x:X) in B"

Here we first need to resolve overloading i.e. find in type C method that accepts type closest to Z. It is B's

def g(x:X):String = super.f(x) + ", " + "g(x:X) in B"

We can see that this method is not overridden in C so it will produce output. super.f(x) means A.f(x) since B extends A

println(c.h(z)) = "f(x:X) in ObjB, g(y:Y) in ObjB, h(y:Y) in B, h(z:Z) in C"

Here we first need to resolve overloading i.e. find in type C method that accepts type closest to Z. It is C's

def h(z:Z):String = super.h(z) + ", " + "h(z:Z) in C"

This give us last part of the answer. Now super.h(z) means B's

def h(y:Y):String = B.g(y) + ", " + "h(y:Y) in B"

because there is no h(Z) in the B so we need to search for methods that accept base types of Z. This gives us second to the last part of the answer. Now B.g(y) is a call of object B's

def g(y:Y) = f(y) + ", " + "g(y:Y) in ObjB"

This is so because in the context of h(y:Y) declared type is Y rather than original (and actual) Z. Obviously here f(y) is a call of object B's

def f(x:X) = "f(x:X) in ObjB"

println(c.k(x)) = "f(y:Y) in C, m(a:A) in Y, k(x:X) in C"

Again we first need to resolve overloading i.e. find in type C method that accepts type closest to X. It is C's

def k(x:X):String = x.m(this) + ", " + "k(x:X) in C"

This gives us last part of the answer. Now resolve x.m(this): we need to find in X method m that accepts type closest to C:

def m(a:A) = a.f(this) + ", " + "m(a:A) in X"

However this is the first time where overriding steps in. Actual type of x here is Y so the call will be to Y's

override def m(a:A) = a.f(this) + ", " + "m(a:A) in Y"

Now we need to resolve a.f(this). this here has a declared type of Y so

def f(y:Y):String = "f(y:Y) in A"

is a match in A but again this method is overridden in C so

override def f(y:Y):String = "f(y:Y) in C"

will be selected.