Inheritance is a fundamental concept in object-oriented programming that allows classes to inherit methods and properties from other classes. While inheritance provides a great deal of flexibility and code reuse, it also has its limitations. One such limitation is the diamond inheritance problem, which occurs when a class inherits from two or more classes that share a common ancestor, resulting in ambiguity during compilation.
The diamond inheritance problem has been a long-standing issue in language design, and it has led to various innovative solutions in different programming languages. In this article, we will delve into the diamond inheritance problem in more detail and see why its problematic, explore how Scala addresses it using a process called linearization, and finally see how traits in Scala capitalize on linearization to provide a powerful feature called stackable modifications.
Diamond inheritance problem
Consider a class A that has two subclases, B and C, and a subclass D that inherits from both B and C.
When B and C each override a method from A with the same signature, then D will inherit both methods, resulting in an ambiguity in the method resolution order. It is unclear which method implementation should be used when an object of class D calls the inherited method.
Another issue that arises is with constructors. If both B and C's constructors call A's constructor, then D's constructor will call A's constructor twice, leading to two instances of A, and, naturally, unexpected behavior.
Languages deal with the diamond inheritance problem in different ways. C++ solves this using a concept called virtual inheritance, which uses the virtual keyword to indicate that a class should be treated as a virtual base class, which ensures that only one instance of the shared superclass is created. C++ also requires the derived class to explicitly specify which version (from which parent) of the inhereted method to be called by providing an override for it.
In Java, the diamond inheritance problem is avoided altogether by prohibiting multiple inheritance. Instead, Java allows classes to implement multiple interfaces, which do not contain constructors, concrete methods, or fields and therefore do not present the problems associated with diamond inheritance. However, the introduction of default methods in Java 8 allows interfaces to have methods with a concrete implementation. If a class implements two interfaces, each with a default method with the same signature, it will result in a compilation error. To overcome this, the class must provide an override for the method, explicitly selecting from which interface to use the default method. This approach ensures that there is no ambiguity or conflict between the default methods of the interfaces being implemented.
Scala follows a similar approach as Java by disallowing multiple inheritance, but it provides the flexibility to mix in multiple traits. Traits in Scala are akin to interfaces in Java, but they can also include fields and concrete methods. Unlike classes, however, traits do not have constructors. This leads to one issue with diamond inheritance, that of method resolution. To tackle this, Scala employs a technique called linearization. It determines the order in which traits are mixed in, which in turn governs the order in which methods are resolved.
Mixing in multiple traits
Let's look at some Scala code to see this in action:
abstract class Person {
def name: String
}
trait Student extends Person {
override def name: String = "student"
}
trait Alumni extends Student {
override def name: String = "alumni"
}
trait Employee extends Person {
override def name: String = "employee"
}
Here, we define an abstract class Person with a method name and three traits that all inherit from the Person superclass (directly and indirectly) and override the name method.
Next, we create a subclass TeachingAssistant and mix in two traits, Employee and Alumni:
class TeachingAssistant extends Person with Employee with Alumni
Since both traits inherit from the superclass Person, this results in a diamond shape in the inheritance hierarchy, as depicted below:
The crux of the problem here is that the TeachingAssistant class inherits from two traits, Employee and Alumni, that both override the same name method. This presents a dilemma: which implementation of name should the TeachingAssistant class use?
Let's see what happens by creating an instance of TeachingAssistant and calling the name method:
val assistant = new TeachingAssistant()
println(assistant.name) // alumni
Why was "alumni" printed instead of "employee" or "student"? This is due to the order in which the traits are mixed in.
Linearization
When instantiating a class in Scala using new, the class and all its inherited traits are arranged in a linear order by a process called linearization. This linear order is then used to determine which method to call when there is a conflict.
The process of linearization can be quite complicated to understand as it involves a precise order of mixing in traits. In Wikipedia, it is described as "a right-first, depth-first search of extended traits, before eliminating all but the last occurrence of each module in the resulting list". As if that wasn't difficult enough to understand, the Scala language specification doesn't make it any simpler.
After scratching my head for a few hours and embedding the concept, I present you my understanding of linearization, which I find simpler to follow.
Determining the linearization order
We first need to start computing the linearization from left to right of the class definition. Let's remind ourselves of the TeachingAssistant class again:
class TeachingAssistant extends Person with Employee with Alumni
Moving from left to right, we first look at the superclass Person. To determine its linearization, we start with Person in the inheritance tree and move upwards until we can't go any further. Because Person doesn't explicitly extend a superclass, it by default extends AnyRef, which in turn extends Any. Thus, the linearization of Person is:
Moving further right in the class definition, we find the first mix-in, the Employee trait. We compute its linearization the same way as Person, but we ignore any classes or traits that have already been seen in previous linearizations:
We repeat the same process for the next and final trait, Alumni. Again, we ignore anything we've seen in previous linearizations:
Now that we have the linearization of the superclass and all the subsequent traits, we can form the linearization of TeachingAssistant. All we need to do is start with the class itself and chain onto it all previously seen linearizations in reverse order:
Therefore, the linearization of TeachingAssistant is:
TeachingAssistant -> Alumni -> Student -> Employee -> Person -> AnyRef -> Any
By looking at this order, we know that when TeachingAssistant invokes a method, the implementation invoked will be the first implementation to its right, which, as we can see, is Alumni, matching the output of "alumni" we saw earlier.
While this is a simple example, linearization can get quite complicated when there are multiple traits and classes involved. However, the process of linearization is always the same: start from the class definition and move from left to right, computing the linearization of each class and trait, before finally chaining them in reverse order.
Linearization gets more interesting when we start to mix in traits that call super in their implementations, allowing us to combine the behaviors of each method.
Stackable modifications
A key use of traits in Scala is to enable stackable modifications, which allow us to additively modify the behavior of a class by stacking traits on top of each other.
For example, let's say we have a logger class with a single method called log that writes to the console. We can define three traits to modify the logger's behavior:
- Timestamp: adds a timestamp to each log line
- Uppercase: uppercases the log line
- Prefix: adds a prefix to each log line
Each trait represents a modification to the behavior of the logger class, and they can be stacked on top of each other to create a new class with any combination of the modifications applied.
By mixing in these traits, we can create a customized logger with the desired modifications. For example, if we mix in the timestamp and prefix traits, we get a logger that includes timestamps and prefixes in each log line. This enables extensible and reusable code, as we can easily modify the behavior of a class without having to modify the class itself.
Defining the base class
Let's see how this actually works by writing some code. First, we define an abstract logger class and a concrete implementation:
abstract class Logger {
def log(msg: String)
}
class ConsoleLogger extends Logger {
def log(msg: String) = println(msg)
}
The ConsoleLogger class provides an implementation of Logger that writes the log message to the console. We'll be mixing in traits into this class to alter its behavior.
Defining the traits
Next, let's define the three traits mentioned earlier:
trait TimestampLogger extends Logger {
abstract override def log(msg: String) {
super.log(s"${java.time.Instant.now()} $msg")
}
}
trait UppercaseLogger extends Logger {
abstract override def log(msg: String) {
super.log(msg.toUpperCase())
}
}
trait PrefixLogger extends Logger {
val prefix: String
abstract override def log(msg: String) {
super.log(s"$prefix $msg")
}
}
It's important to note that the traits contain a super call on a method that is declared abstract. While such a construct would be illegal in normal classes, it is allowed in traits because traits are dynamically bound when defining a class. However, this only works if the trait is mixed in after another trait or class that provides a concrete implementation of the abstract method. In our case, we'll be mixing the traits into the ConsoleLogger, which contains a concrete implementation of log.
This is common when using traits for stackable modifications. To indicate to the compiler that we are intentionally using this pattern, we must mark these methods as abstract override. This combination of modifiers is only valid for members of traits, not classes, and signals that the trait must be mixed into a class that has a concrete implementation of the method.
Mixing in the traits
Let's start using the traits to create our custom logger. First, we mix in the TimestampLogger and UppercaseLogger traits:
val logger = new ConsoleLogger with TimestampLogger with UppercaseLogger
logger.log("cowabunga") // 2023-04-20T23:12:18 COWABUNGA
The order in which mixins are applied is crucial as it affects the linearization of the resulting ConsoleLogger class, which will determine the order in which the methods are invoked. Remember that we're chaining methods together by calling super, which means that the invocation won't stop at the first trait in the linearization but will continue through to the end of the linearization chain (or until super is no longer called).
As a result, we can see that both traits were utilized (timestamp was added plus the message was uppercased), in addition to the superclass (which actually logged the message to the console), and their order was determined by linearization.
Consider another example where we mix in the TimestampLogger and PrefixLogger:
val logger = new ConsoleLogger with TimestampLogger with PrefixLogger {
override val prefix: String = "APP"
}
logger.log("cowabunga") // 2023-04-20T23:12:18 APP cowabunga
We can see that the prefix mix-in is applied before the timestamp, since the prefix "APP" appears after the timestamp in the log line.
Let's reverse the order of the mix-ins:
val logger = new ConsoleLogger with PrefixLogger with TimestampLogger {
override val prefix: String = "APP"
}
logger.log("cowabunga") // APP 2023-04-20T23:12:18 cowabunga
We can see how changing the order of the mix-ins has made that the prefix mix-in apply after the timestamp. I leave it as an exercise for the reader to calculate the linearization of the above example and validate it against the output.
Conclusion
This article explains the diamond inheritance problem and how it manifests in Scala when using traits. We saw how traits provide a limited form of multiple inheritance and how Scala's linearization process eliminates ambiguity by creating a linear order of class and trait composition. This not only gives rise to deterministic method resolution but also allows traits to be stacked with each other with the use of super. While understanding linearization can be a bit tricky, it's important to understand how it works in order to use and compose traits effectively.
This is just one of the many powerful features of Scala that make it a complex but flexible language. The more I learn about Scala, the more I appreciate its elegance. What are your thoughts about the language? Let me know in the comments below!