C3 Superclass Linearization (Optional)
00:00 In the last video, you learned that Python uses the method resolution order, or MRO, to determine what order to search parent classes for the desired method. In Python 3, the algorithm that generates the MRO is called the C3 superclass linearization algorithm, or C3 for short.
00:32 The algorithm is best explained with an example. This UML diagram on the right should look pretty familiar by now. Understanding the MRO becomes crucial when trying to patch fix the diamond problem, as you saw in the last video.
This video will explain why that is. In this example, assume that
TemporarySecretary inherits from
Secretary, and then
HourlyEmployee, as seen in red. Linearization is the process of generating an ordered list of classes, aka the MRO. As I mentioned before, each class has its own linearization.
01:30 This process is recursive, as each class’s linearization relies on the linearization of its parents. The linearization of the base class, which can be seen as the base case of this recursion, is just itself.
We’re going to start at the top with
Employee and work our way down until we have the linearization for
TemporarySecretary. The linearization of the base class is just itself, which I will list as E. Next, let’s compute the linearization of
SalaryEmployee, or SE. The order of this computation doesn’t matter, so long as we linearize all the classes from top to bottom.
Each linearization starts out with itself plus this merge() function. You’ll understand how the merge() function works as we go on, but for now, just know that the merge() function will take in the linearizations of the parent classes plus a list of those classes in the same order. For
Now that the merge() arguments are all simplified, we can start merging them into the list on the left, one by one. In the case where the merge() function contains just one class, it will merge this class with the list on the left, and that is the entire linearization of
SalaryEmployee. Intuitively, this makes sense.
We know that when you use the
.__init__() method to construct an object out of this class, Python will try to use the
.__init__() method in
SalaryEmployee, and if one doesn’t exist there, it will search
Employee for one.
04:48 As long as that first item isn’t not the first item in the remaining lists, it will pull that item out of all the lists and merge it with the list on the very left. In this case, SE is the first item of two lists, so we’ll pull that out and merge it with the list on the left.
Then, when the merge() function has just a single class, it gets merged with the list on the left automatically. The linearization of
SalaryEmployee, and then
Employee, as you might’ve expected. Finally, we can linearize
05:37 This involves multiple inheritance, meaning that things are going to start getting a little bit more interesting. As usual, we have the sum of the class itself, plus the merging of its parents’ linearizations, and a list of parents themselves.
05:56 This is why the order of inheritance matters. If we swapped L(S) and L(HE), we would get a different result. As usual, I will simplify those linearizations and now we are left with three lists to merge.
07:09 As a final note, there are cases where this algorithm can fail, and if that happens, Python will raise an exception. One example of this is with cyclical inheritance, which will ultimately result in infinite recursion and a stack overflow.
Become a Member to join the conversation.