This content originally appeared on Level Up Coding - Medium and was authored by Irina Moonin
How Python supports multiple inheritance using C3 linearization and why the base classes' order is critical.
The Deadly Diamond of Death - the most known multiple inheritance problem, arises when class A inherits from two classes B and C, which both inherit from a base class D. For a method foo() in class D, class A will inherit two copies of it - one from each parent. So which copy will be invoked for an object a of class A when one calls for a.foo()? The answer depends on the linearization algorithm.
Method Resolution Order (MRO) is an algorithm for the construction of linearization - the list of all the ancestors of a class, including the class itself, ordered from the closest to the furthest. This is the order in which methods and attributes are looked up. While linearization is trivial for single inheritance, it becomes sophisticated for multiple inheritance.
A key requirement from an MRO is monotonicity: if class B appears before class C in the linearization of class A, then B should appear before C in the linearization of any class derived from A. otherwise, creating a subclass may change the resolution order and introduce nasty bugs. Before version 2.3, Python used a native algorithm however it was discovered as not monotonic. In Python 2.3 the native algorithm was neglected in favor of the academically developed C3 linearization, which moved on to Python 3.
Obtaining the MRO for object a of class A is as simple as calling a.mro(), however, if you are interested in how the computation is actually performed, keep on reading.
C3 applies the divide and conquer approach to calculate linearization in the following way: let A be a class that inherits from the base classes B1, B2, … Bn. The linearization of A is the sum of A plus the merge of the linearizations of the parents and the list of the parents:
L[A(B1 … Bn)] = A + merge(L[B1] … L[Bn], B1 … Bn)
To perform the merge:
- Look at the head of the first list: L[B1][0]
- If this head is a “good head”, means that it does not appear in the tail of any other list - add it to the linearization of A and remove it from all the lists in the merge.
- Otherwise, look at the next list’s head and if it is a “good head”, add it to the linearization
- Repeat until all the classes are removed or there are no good heads left. In the latter case, the construction fails.
Sounds obscure? let’s clarify it with the following example:
The linearization computation for this hierarchy using the C3 algorithm will look like this:
L[A] = A + merge(L[B], L[C], BC)
In order to compute L[A] we will first have to compute its components: L[B] and L[C]:
The computation of L[C] is similar:
Now L[A] can be computed:
In this case, as in most cases, the linearization “makes sense”: the lower, more specialized classes appear earlier in the hierarchy than the higher and more general classes. However, this is not always the case. To illustrate this, let us introduce only a minor change in the previous example and swap the order of base classes for class B:
let’s compute L[A] for the modified hierarchy, starting with recomputing L[B]:
Not only that the order of the whole hierarchy has changed, now a more general class E appears before a more specific class C! This emphasizes the careful attention that should be paid when designing complex multiple inheritance hierarchies.
So, what about the Deadly Diamond of Death? In Python, this structure is unavoidable and appears in every multiple inheritance hierarchy because all classes are inheriting from the object class.
Fortunately, C3 assists to skillfully resolve this issue:
However, not every possible hierarchy can be linearized while keeping monotonicity:
This will result in: TypeError: Cannot create a consistent method resolution order (MRO) for bases X, Y. This is because the method resolution order is ambiguous for class C: the order of X and Y is unclear in C’s linearization. C3 algorithm fails to linearize the hierarchy and Python prevents its creation. This is another example of the significance of the base classes order.
Resources:
- A detailed article By Michele Simionato that became a part of Python 2.3 documentation, explaining the reasons behind the transition to C3, and the algorithm in detail:
The Python 2.3 Method Resolution Order
2. Guido van Rossum’s post in “The History of Python”:
Method Resolution Order in Python was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Irina Moonin
Irina Moonin | Sciencx (2021-08-03T15:16:45+00:00) Method Resolution Order in Python. Retrieved from https://www.scien.cx/2021/08/03/method-resolution-order-in-python/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.