The C3 Algorithm and the mro

To make things easier we have to linearize the inheritance so that it looks like the chain of superclasses that we have in single inheritance. The idea is that you need to create an order that the classes are searched to find an attribute in the mro.

You can see that some of the classes are more basic than others – they are naturally earlier in the inheritance chain. In Python 2 a simple left to right depth first method was used, but in Python 3 (and 2.3 on for new classes) the C3 method which has much better properties is used.

For example in:

It is reasonable that B and C would have more attributes than A as they are derived from A. In this sense A comes earlier in the inheritance chain and B and C should be searched first for attributes, and then A.

Our first principle is that no base class should appear in the mro before its child classes. That is A, should not appear before B or C.

Clearly A should only be searched once and this is the second principle: no duplicate classes in the mro.

Which of B or C should be searched first?

There is no absolute answer to this but Python uses the idea that the order that you specify classes should be important.

That is, the classes should appear in the mro in the same order that they appear in the class definition reading left to right.

So if you are specifying:

class D(C,B)

then C should come before B in the mro:

D → C → B → A 

but if you define:

class D(B,C)

then B should come before C:

D → B → C → A

The final principle is the most sophisticated – the mro should be monotonic.

That is, if C1 precedes C2 in the mro of C, then this is true in the mro of any subclass of C. That is, adding a class to the mro doesn’t change the order of what you already have. It might insert a class between two existing classes, but it never changes the order of two classes.

This makes any decisions you have made based on the mro for class C valid for a class derived from C.

To sum up, the C3 algorithm produces an mro that:

• has no base classes before their child classes

• each class is only included once

• the local left to right order used in the class declaration is preserved. If A is to the left of B in a class declaration then it will be earlier in the mro.

• The mro is monotonic in that subclassing an existing class does not change the order of classes in the existing mro.

The C3 algorithm was invented as part of the Dylan language and it is used in Perl as well as Python.

Notice that there are inheritance graphs that cannot be linearized and in this case Python will display an error message. The correct response to this is to consider what is wrong with the proposed inheritance and change it.

You should only ever use multiple inheritance that is linearizable by the C3 or a similar algorithm to give the desirable properties listed earlier.

Computing the C3 mro

Final version in book.

Getting to Know Linearization

Final version in book.

Calling Super Cooperative Multiple Inheritance

Final version in book.

The Dwindling Parameter Pattern

Final version in book.

Summary

• Single inheritance doesn’t satisfy all of the requirements of domain modeling and doesn’t allow for modifications to inheritance chains to introduce otherwise useful mixin classes.

• Multiple inheritance is superficially easy but it changes the hierarchy of classes into a more general graph where each class can be inherited more than once – the so-called diamond problem.

• If you recast the idea of multiple inheritance as a way of modifying inheritance chains then the solution to the diamond problem is to linearize the inheritance graph to produce an inheritance chain in the form of the mro.

• The C3 algorithm can produce a linearized inheritance chain that has good properties.

• Not all cases of multiple inheritance can be linearized using C3, but these are problematic and best avoided.

• Once you understand how the mro is constructed you can start to control the way that multiple inheritance determines the mro and you can make informed choices of how to define the inheritance.

• The resulting mro allows each class to have a unique superclass and the super() function makes use of this to return a single superclass for any class in the mro.

• However, as the inheritance chain can vary, a given class may have a different superclass depending on which mro you are using.

• To make cooperative multiple inheritance work you have to make sure that each class calls the __init__ of its superclass and makes use of the dwindling parameter pattern to allow for the superclass to vary.

Programmer's Python
Everything is an Object
Second Edition

Is now available as a print book: Amazon

Contents

1. Get Ready For The Python Difference
2. Variables, Objects and Attributes
3. The Function Object
4. Scope, Lifetime and Closure
     Extract 1: Local and Global ***NEW!
5. Advanced Functions
6. Decorators
7. Class, Methods and Constructors
     Extract 1: Objects Become Classes 
8. Inside Class
9. Meeting Metaclasses
10. Advanced Attributes
11. Custom Attribute Access
12. Single Inheritance
13. Multiple Inheritance
14. Class and Type
15. Type Annotation
16. Operator Overloading
17. Python In Visual Studio Code

 Extracts from the first edition

<ASIN:1871962749>

<ASIN:1871962595>

<ASIN:1871962765>

Related Articles

Creating The Python UI With Tkinter

Creating The Python UI With Tkinter - The Canvas Widget

The Python Dictionary

Arrays in Python

Advanced Python Arrays - Introducing NumPy

<ASIN:1871962587>