Blog
Functional Programming
Scala: Linearization technique to avoid multiple inheritance

ScalaTo support inheritance Scala has introduced a concept called trait almost similar to Java`s interface. But unlike Java interfaces, Scala traits can actually define any concrete methods. From this it seems apparently that Scala supports multiple inheritance; but that is not the case. To avoid multiple inheritance Scala uses a technique called linearization to flatten the calls to super classes.

 

To illustrate this linearization technique we will use some Scala classes mixed-in with Scala Traits as per the below inheritance structure:

Linearization technique

Now, say, BaseClass has a function print and each of the traits as well as the DerivedClass overrides the print function and also calls the print function of the super class. So the class/trait definitions are as follows:

Linearization technique

So the question is, if we call the print function of the DerivedClass then what will be the call flow of the print function of the super classes. (Please note that each of the overridden function in each class/traits has a call to the print function of the super class)

If Scala would have supported multiple inheritance then the above calls should create an ambiguity as we are not sure which of the print functions will get called or even whether the print function of the base class would get called thrice. But Scala avoids this ambiguity by linearization.

Scala Linearization technique uses the following equation to flatten the calls to the super classes and avoid multiple inheritance (Reference Scala Language Specification Section 5.1.2):

Linearization technique

Where +: denotes a concatenation function where elements at right hand operand replaces identical elements of the left hand operand as follows:

Linearization technique

Also C1... Cn denotes the inherited classes/traits in order they are declared for the class from left to right.

We will use our sample class hierarchy to explain the above linearization equation.

If we want to find out the linearization structure of or DerivedClass defined as

Linearization technique

then the above parameters of linearization for this DerivedClass would be:

Linearization technique

And then the linearization equation for the DerivedClass will be:

Linearization technique

Now we will apply the same equation for all other classes and traits.

So for BaseClass the definition is

Linearization technique

So the linearization equation of BaseClass would be

Linearization technique

(NOTE: Though we didn`t added any super class of BaseClass, but as per Scala hierarchy the default super class of any Scala class is scala.AnyRef, similarly scala.AnyRef extends scala.Any)

Now if we simplify this we will get the following:

Linearization technique

Applying same equation for Trait1 which is defined as:

Linearization technique

the linear form will be:

Linearization technique

Similarly for Trait2 and Trait3 we get:

Linearization technique

And

Linearization technique

So we get the following linear form of all the classes/traits:

Linearization technique

Except for the DerivedClass all other classes/traits have the linear form. Let us now use the equation to linear the DerivedClass

Linearization technique

If we simplify the above equation and apply the `+:` operation then we get the following equation:

Linearization technique

Just to explain the above simplification logic we are using the +: operation which is defined as

Linearization technique

So for,

Linearization technique

the "BaseClass, scala.AnyRef, scala.Any" of the left operand is removed since the right operand also has the same and the result is

Linearization technique

So the final linear form of the DerivedClass is:

(DerivedClass, Trait3, Trait2, Trait1, BaseClass, scala.AnyRef, scala.Any)

If we call the print function of the DerivedClass we will get the following output:

Linearization technique

This proves that when we call the print function of the DerivedClass and since each of the classes/traits has a call to super.print the call will follow the above linear sequence and thus Scala avoids multiple inheritance.

Following diagram shows the inheritance and the linearization for our sample classes/traits: enter image description here

Linearization technique

The linear form of a class hierarchy will depend on the order of the traits imported. For example if we change the definition of our DerivedClass from

Linearization technique

to

Linearization technique

and then apply the above series of equations then we will get a different linear form of our DerivedClass which will be:

Linearization technique

So the conclusion is that the definition of a trait does not define the linear form, instead how it is mixed-in with a class defines the actual linear form.

Dipta P. Banerjee

Comment(s)
Name :
Email :
Comment :