Method resolution order in Python
This note discusses the MRO C3 algorithm and some specific problems of multiple inheritance. Although the algorithm and problems are not limited to the framework of one language, I focused on Python. At the end is a list of useful links on this topic.
The method resolution order allows Python to figure out which ancestor class to call the method from if it is not found directly in the descendant class. If each descendant has only one ancestor, then the task is trivial. An upward search occurs throughout the hierarchy. If multiple inheritance is used, then you may encounter specific problems, which are described below.
In older versions of Python, the order of method resolution was quite primitive: the search was conducted in all parent classes from left to right to the maximum depth. Those. if the parent class, in turn, did not have the desired method, but had parents, then the search was carried out in them according to the same rules. For example, take the structure:
When referring to an instance method of class E, such an algorithm would search sequentially in classes E, B, A, D, and C. Thus, the search was conducted first in the first parent class and in all its ancestors, then in the second parent class with all ancestors etc. This method did not cause any particular complaints until the classes had a common ancestor. However, starting with version 2.2, the base class object appeared, from which it was recommended to inherit all user classes. Why it was introduced is a topic for a separate article. Perhaps the most significant factor is the separation of the object model and the meta-data model. Starting with version 3.0, old classes are no longer supported, and all user classes by default come from the object class.
This gave rise to the “diamond diagram” problem.
If we have classes A and B, from which class C is inherited, then when searching for a method using the old algorithm (C, A, object, B), it turns out that if the method is not defined in classes C and A, it will be extracted from object, even if it is defined in B. This creates certain inconvenience, because object defines many magic methods, such as __init__, __str__, etc. But even if you replace object with a certain user class D, the problem remains - the less specific method of the ancestor class can work out instead of the more specific method of the descendant class.
So, we have in our hands the class itself, a list of all its ancestors and the connections between them. From this data we need to build an ordered list of classes in which the method will be searched from left to right. Such a list is called class linearization. For simplicity, we take the structure:
Then the linearization for class B will be the list [B, A, object]. Those. when B (). something () is called, the method will first be searched in class B. If it is not found there, then the search will continue in class A. If it is not there, then the search will end in the class object. After going through all the classes from linearization and not finding the desired method, Python will throw an Attribute Error.
To solve the problem of the rhomboid structure, linearization should be monotonic. This means that if in the linearization of a certain class C class A follows class B (it has the form [C, ..., B, ..., A]), then for any of its descendants D class B will follow A in its linearization ( it will look like [D, ..., C, ..., B, ..., A]). As you can see, the old order of method resolution is not monotonous, because in the case of a rhomboid structure for class A, the linearization is [A, object], for class B it is [B, object], but for class C it is [C, A, object, B], which violates the monotonicity property with respect to class B.
To satisfy the monotonicity property, in this case two linearizations are suitable: [C, A, B, object] and [C, B, A, object]. Obviously, both of them do not violate monotony with respect to either class A (because object follows A in both cases) or class B (since object follows B in both cases). So which one to choose? In this case, the most intuitive way is to look at the definition of the class C. If the class is declared as C (A, B), then it is wise to take the first linearization, since B follows A. In it. If the class is declared as C (B, A ), then it would be better to take the second linearization, in which A follows B.
This choice is determined by the local precedence ordering. The property of the order of local precedence requires observance for parent classes in the linearization of the descendant class of the same order as when it was declared. For example, if a class is declared as D (A, B, C), then in the linearization of D, class A should be before B, and class B should be before C.
To summarize the intermediate results:
To achieve the above goals, Python uses the C3 algorithm. It is quite simple, but for a better understanding we introduce the following conventions:
[C1, C2, ... CN] - a list of elements C1, C2, ... CN. Accordingly, [C] is a list of one element C.
L [C] is a linearization of class C. It is important to remember that any linearization is a list by definition.
merge (L [C1], L [C2], ..., L [CN]) - merge the linearization elements L [C1], L [C2], ..., L [CN] into a list using some algorithm. In fact, this algorithm should sort all classes from L [C1], L [C2], ..., L [CN] and exclude duplication of classes in the final list.
Algorithm C3 is a set of the following rules:
L [C] = [C] + merge (L [A], L [B], [A, B])
L [A] = [A] + merge (L [object], [object ])
L [B] = [B] + merge (L [object], [object])
L [object] = [object] (degenerate case)
The merging process is of the greatest interest, so we will analyze it in more detail. In the cases L [A] and L [B], the expression merge (L [object], [object]) = merge ([object], [object]) is expanded trivially. Since both the first and second lists consist of one object element, according to clause 4 of the union rule, the result will be [object].
Now let's parse L [C] = [C] + merge (L [A], L [B], [A, B]) = [C] + merge ([A, object], [B, object], [A , B]). We will write our union according to the rules of C3:
We write the linearization L [C]:
L [C] = [C] + merge (L [D], L [E], [D, E])
L [E] = [E] + merge (L [D], [D])
L [D] = [D] + merge (L [object], [object]) = [D, object]
Let's make the substitutions and get:
L [E] = [E] + merge ([D, object ], [D]) = [E, D, object]
L [C] = [C] + merge ([D, object], [E, D, object], [D, E])
Now look what we got. Merge merging ([D, object], [E, D, object], [D, E]) cannot be completed, because in the lists [D, object] and [D, E], the zero element is D, which is the first list item [E, D, object]. Conversely, E, which is the null element of [E, D, object], is also the first element of [D, E]. Thus, after 3 iterations, the algorithm will come to step 5, after which Python will throw a TypeError error: Cannot create a consistent method resolution order (MRO) for bases D, E. If our union did not end with the list of parents, we would get a violation of the order local seniority: L [C] = [C] + merge ([D, object], [E, D, object]) = [C] + [E] + merge ([D, object], [D, object] ) = [C] + [E, D] + [object] = [C, E, D, object]. With such a linearization of class C, the search would be conducted first in class E,
To solve this problem is not difficult. It is enough to rewrite the declaration in class C (E, D). In this case, we get:
L [C] = [C] + merge ([E, D, object], [D, object], [E, D]) = [C] + [E] + merge ([D , object], [D, object], [D]) = [C] + [E, D, object] = [C, E, D, object].
In fact, nothing has changed, except that in the class declaration, the order of listing the parents is the same as in the linearization of the class, i.e. the order of local seniority is respected. It should be noted that although Python is hinting in what order it would be more logical to indicate the parents, it will not stop you from looking for adventure if you declare your own MRO through a metaclass. But more about that near the end.
Python computes linearization once when creating a class. If you want to get it for self-testing or for some other purposes, use the __mro__ class property (for example, C .__ mro__). To consolidate the material, let’s take a look at the examples that are poorer. The object class is intentionally thrown out so as not to clutter up the linearization. As is known from the above, with single inheritance, classes simply line up from descendant to ancestors, so that the object will always be at the end of any chain. And further. I am not a culinary specialist or a musician, so examples are just examples. You should not focus on semantic inaccuracies in them.
L [The69Eyes] = [The69Eyes] + merge (L [GothicRock], L [GothicMetal], [GothicRock, GothicMetal])
L [GothicRock] = [GothicRock] + merge (L [Rock], L [Gothic], [Rock , Gothic])
L [GothicMetal] = [GothicMetal] + merge (L [Metal], L [Gothic], [Metal, Gothic])
L [Rock] = [Rock, Music]
L [Gothic] = [Gothic, Music ]
L [Metal] = [Metal] + [Rock, Music] = [Metal, Rock, Music]
After the substitutions we get:
L [GothicRock] = [GothicRock] + merge ([Rock, Music], [Gothic, Music], [Rock, Gothic]) = [GothicRock, Rock, Gothic, Music]
L [GothicMetal] = [GothicMetal] + merge ([Metal, Rock, Music], [Gothic, Music], [Metal, Gothic]) = [GothicMetal ] + [Metal, Rock, Gothic, Music] = [GothicMetal, Metal, Rock, Gothic, Music]
L [The69Eyes] = [The69Eyes] + merge ([GothicRock, Rock, Gothic, Music], [GothicMetal, Metal, Rock, Gothic, Music], [GothicRock, GothicMetal])
= [The69Eyes] + [GothicRock, GothicMetal] + merge ([Rock, Gothic, Music], [Metal, Rock, Gothic, Music])
= [The69Eyes] + [GothicRock, GothicMetal, Metal] + merge ([Rock, Gothic, Music], [Rock, Gothic, Music] )
= [The69Eyes, GothicRock, GothicMetal, Metal, Rock, Gothic, Music]
L [Pie] = [Pie] + merge (L [Rabbit], L [Pork], L [Pasty], [Rabbit, Pork, Pasty])
L [Rabbit] = [Rabbit] + merge (L [Meat], [Meat])
L [Pork] = [Pork] + merge (L [Meat], [Meat])
L [Pasty] = [Pasty] + merge (L [Milk], L [Flour], [Milk, Flour] )
L [Meat] = [Meat] + merge (L [Food], [Food]) = [Meat, Food]
L [Milk] = [Milk] + merge (L [Food], [Food]) = [Milk , Food]
L [Flour] = [Flour] + merge (L [Food], [Food]) = [Flour, Food]
After the substitutions we get:
L [Rabbit] = [Rabbit, Meat, Food]
L [Pork] = [Pork, Meat, Food]
L [Pasty] = [Pasty] + merge ([Milk, Food], [Flour, Food], [Milk, Flour]) = [Pasty] + [Milk, Flour, Food] = [ Pasty, Milk, Flour, Food]
L [Pie] = [Pie] + merge ([Rabbit, Meat, Food], [Pork, Meat, Food], [Pasty, Milk, Flour, Food], [Rabbit, Pork, Pasty])
= [Pie] + [Rabbit] + merge ([Meat, Food], [Pork, Meat, Food], [Pasty, Milk, Flour, Food], [Pork, Pasty])
= [Pie] + [Rabbit, Pork] + merge ([ Meat, Food], [Meat, Food], [Pasty, Milk, Flour, Food], [Pasty])
= [Pie] + [Rabbit, Pork, Meat] + merge ([Food], [Food], [Pasty , Milk, Flour, Food], [Pasty])
= [Pie] + [Rabbit, Pork, Meat, Pasty] + merge ([Food], [Food], [Milk, Flour, Food])
= [Pie] + [Rabbit, Pork, Meat, Pasty, Milk, Flour, Food]
= [Pie, Rabbit, Pork, Meat, Pasty, Milk, Flour, Food]
Multiple inheritance poses another specific problem. Actually, a direct search for some method in the parent classes is only part of the benefits that can be derived from it. As in the case of single inheritance, you can often make your life easier by implementing a method in a descendant that, in addition to some actions, will call the same parent method. For example, you can often find this: However, for the case of multiple inheritance, this approach is not suitable. And for what reasons:
First, we explicitly refer to the parent classes (in fact, the same is true in the case of single inheritance). If we want to replace one of our ancestors with another class or remove it altogether, then we will have to change all the functions that accessed it. This is fraught with bugs if we miss something. But this is still half the trouble. Secondly, we do not know anything about classes A and B. Perhaps they have common ancestors, which they refer to in the same way: If so, then it turns out that the initialization of the common ancestors will work twice. It is not right. To avoid this, Python has a super class. In version 3.0, he is finally humanized and can be accessed as follows:
Note that in versions 2.x, the first argument must specify the class itself, and not any of its parent. In fact, the super class object remembers the arguments passed to it at the time of initialization and, when calling any method (super () .__ init __ (self) in the example above) goes through the linearization list of the second argument class (self .__ class __.__ mro__), trying to call this method in turn for all classes following the class in the first argument (class C), passing the first argument (self) as a parameter. Those. for our case:
self .__ class __.__ mro__ = [C, B, A, P1, P2, ...]
super (C, self) .__ init __ () => B .__ init __ (self)
super (B, self) .__ init __ ( ) => A .__ init __ (self)
super (A, self) .__ init __ () => P1 .__ init __ (self)
As you can see, from the B .__ init__ method, when using super, the A .__ init__ method will be called, although the class A has nothing to do with it and is not its ancestor. In this case, if necessary, the chain will work out the methods of all ancestors once.
Thanks to this approach, you can, for example, introduce the allergen method for all components for the examined pie example, which will consistently go through the chain of ancestors to make a list of all allergen components in order to warn buyers. It will be convenient instead of rewriting the “not recommended” list for each product just to inherit it from its constituent components. Then the list will be generated automatically. Similarly, it will be possible to offer the user a choice of drinks for each product, or to tweak the weight of the user's preferences on a self-made Internet radio station, going from a specific group to genres with a certain attenuation coefficient.
An example with a pie might look like this (for version 2.x): As a result, we will see the following:
List of allergens:
- Pork-protein
- Milk-protein
List of recommended drinks:
- Mineral water
- Novello wine
- Sovinion wine
- Red wine
- Water
- Cola
Based on this list, you can understand how the linearization list was handled. As you can see, none of the parent methods was called twice, otherwise repetitions would be found in the list of allergens or recommendations. In addition, note that in the oldest Food class, both methods are defined - allergen and drink. The super () call does not perform any checks, so if we try to call a non-existent method, we get an error like AttributeError: 'super' object has no attribute 'allergen'.
The case has already been analyzed above when it was impossible to compose a linearization using the C3 algorithm. However, then the problem was solved by changing the places of the ancestor classes in the declaration of the descendant class. There are other cases in which the linearization is not possible: L [E] = [E] + merge (L [C], L [D], [C, D]) = [E] + merge ([C, A , B], [D, B, A], [C, D]) = [E] + [C, D] + merge ([A, B], [B, A])
As you can see, the conflict turned out to be unsolvable, because in the declaration C the class A is before B, and in the declaration D it is vice versa. Well, from this place you have to go and review the structure. But if you really need to get a quick fast or you just know what you are doing, Python will not limit you. You can define your own linearization through metaclasses. To do this, it is enough to specify the mro (cls) method in the metaclass - in fact, redefine the method of the base metaclass type, which will return the linearization you need. Further, the class declaration differs for version 3.0 and 2.x:
After that, E .__ mro__ = [E, A, B, C, D, object]. Note that if you take responsibility for the MRO, Python does not conduct any additional checks and you can safely search the ancestors earlier than the descendants. And although this is not a desirable practice, but it is possible.
Useful links:
Unifying types and classes in Python 2.2 - about the separation of the object model and the meta-data model. It also discusses MRO, multiple inheritance issues, and super ().
The Python 2.3 Method Resolution Order - C3 algorithm with examples. At the end there is an implementation of the mro and merge functions on pure Python for those who better perceive the code than the text.
A Monotonic Superclass Linearization for Dylan - Comparison of some types of linearization.
Of course, it is impossible to cover all related topics, and perhaps someone has more questions than answers. For example, what are metaclasses, base classes of type and object, and the like. If there is interest, then, over time, I could try to parse such topics:
PS: Thanks to all those who helped me post this topic and personally Goodrone .
The method resolution order allows Python to figure out which ancestor class to call the method from if it is not found directly in the descendant class. If each descendant has only one ancestor, then the task is trivial. An upward search occurs throughout the hierarchy. If multiple inheritance is used, then you may encounter specific problems, which are described below.
In older versions of Python, the order of method resolution was quite primitive: the search was conducted in all parent classes from left to right to the maximum depth. Those. if the parent class, in turn, did not have the desired method, but had parents, then the search was carried out in them according to the same rules. For example, take the structure:
AC | | Bd \ / E
When referring to an instance method of class E, such an algorithm would search sequentially in classes E, B, A, D, and C. Thus, the search was conducted first in the first parent class and in all its ancestors, then in the second parent class with all ancestors etc. This method did not cause any particular complaints until the classes had a common ancestor. However, starting with version 2.2, the base class object appeared, from which it was recommended to inherit all user classes. Why it was introduced is a topic for a separate article. Perhaps the most significant factor is the separation of the object model and the meta-data model. Starting with version 3.0, old classes are no longer supported, and all user classes by default come from the object class.
This gave rise to the “diamond diagram” problem.
object
/ \
Ab
\ /
C
If we have classes A and B, from which class C is inherited, then when searching for a method using the old algorithm (C, A, object, B), it turns out that if the method is not defined in classes C and A, it will be extracted from object, even if it is defined in B. This creates certain inconvenience, because object defines many magic methods, such as __init__, __str__, etc. But even if you replace object with a certain user class D, the problem remains - the less specific method of the ancestor class can work out instead of the more specific method of the descendant class.
So, we have in our hands the class itself, a list of all its ancestors and the connections between them. From this data we need to build an ordered list of classes in which the method will be searched from left to right. Such a list is called class linearization. For simplicity, we take the structure:
object | A | B
Then the linearization for class B will be the list [B, A, object]. Those. when B (). something () is called, the method will first be searched in class B. If it is not found there, then the search will continue in class A. If it is not there, then the search will end in the class object. After going through all the classes from linearization and not finding the desired method, Python will throw an Attribute Error.
To solve the problem of the rhomboid structure, linearization should be monotonic. This means that if in the linearization of a certain class C class A follows class B (it has the form [C, ..., B, ..., A]), then for any of its descendants D class B will follow A in its linearization ( it will look like [D, ..., C, ..., B, ..., A]). As you can see, the old order of method resolution is not monotonous, because in the case of a rhomboid structure for class A, the linearization is [A, object], for class B it is [B, object], but for class C it is [C, A, object, B], which violates the monotonicity property with respect to class B.
To satisfy the monotonicity property, in this case two linearizations are suitable: [C, A, B, object] and [C, B, A, object]. Obviously, both of them do not violate monotony with respect to either class A (because object follows A in both cases) or class B (since object follows B in both cases). So which one to choose? In this case, the most intuitive way is to look at the definition of the class C. If the class is declared as C (A, B), then it is wise to take the first linearization, since B follows A. In it. If the class is declared as C (B, A ), then it would be better to take the second linearization, in which A follows B.
This choice is determined by the local precedence ordering. The property of the order of local precedence requires observance for parent classes in the linearization of the descendant class of the same order as when it was declared. For example, if a class is declared as D (A, B, C), then in the linearization of D, class A should be before B, and class B should be before C.
To summarize the intermediate results:
- a linearization of a class is a list of the class itself and all its ancestors (parents and progenitors) in which the method will be searched in order from left to right.
- Method Resolution Order (MRO) is the way in which class linearization is compiled.
- monotonicity is a property that requires observance in the linearization of the descendant class of the same order of parent classes as in the linearization of the parent class.
- the order of local precedence is a property that requires the linearization of the descendant class to observe the same order of parent classes as in its declaration.
The resolution algorithm for the resolution of C3 methods.
To achieve the above goals, Python uses the C3 algorithm. It is quite simple, but for a better understanding we introduce the following conventions:
[C1, C2, ... CN] - a list of elements C1, C2, ... CN. Accordingly, [C] is a list of one element C.
L [C] is a linearization of class C. It is important to remember that any linearization is a list by definition.
merge (L [C1], L [C2], ..., L [CN]) - merge the linearization elements L [C1], L [C2], ..., L [CN] into a list using some algorithm. In fact, this algorithm should sort all classes from L [C1], L [C2], ..., L [CN] and exclude duplication of classes in the final list.
Algorithm C3 is a set of the following rules:
- Linearization of class C is a singleton list from class C itself plus the union of the linearizations of its parents and the list of all its parents. In the legend, this can be written as L [C] = [C] + merge (L [C1], L [C2], ..., L [CN], [C1, C2, ..., CN]) if the class C was declared as class C (C1, C2, ..., CN). It should be noted that each linearization of L [CX] begins with the class CX, which was additionally assigned to the end of the union list as a direct parent of class C. Why this will be made clear later.
- The linearization is combined as follows:
- The zero element from the first linearization is taken (L [C1] [0]).
- This element is sought in all other linearizations (from L [C2] to L [CN]).
- If this element is found somewhere outside the beginning of the list (L [CK] [X] == L [C1] [0], X! = 0; in essence, this means that L [C1] [0] is someone else’s ancestor), then the algorithm proceeds to the first step, taking as the zero element from the following linearization (L [C2] [0]).
- If the element is not found anywhere in a position other than zero, then it is added to the end of the linearization final list and is removed from all the lists in question (from L [C1] to L [CN]; the same class cannot be found twice in the final list) . If after deleting an item there are empty lists, they are excluded from the union. After that, the algorithm is repeated from the very beginning (from the new element L [C1] [0]), if any. If it is not there, the union is completed.
- If the algorithm reaches the last element of L [CN], but none of the zero elements satisfies the rules, then linearization is not possible.
L [C] = [C] + merge (L [A], L [B], [A, B])
L [A] = [A] + merge (L [object], [object ])
L [B] = [B] + merge (L [object], [object])
L [object] = [object] (degenerate case)
The merging process is of the greatest interest, so we will analyze it in more detail. In the cases L [A] and L [B], the expression merge (L [object], [object]) = merge ([object], [object]) is expanded trivially. Since both the first and second lists consist of one object element, according to clause 4 of the union rule, the result will be [object].
Now let's parse L [C] = [C] + merge (L [A], L [B], [A, B]) = [C] + merge ([A, object], [B, object], [A , B]). We will write our union according to the rules of C3:
- Take the zero element of the first list - A.
- Let's look for it in all other lists, i.e. in [B, object] and [A, B].
- Since class A is not found in the list [B, object], and in the list [A, B] is the zero element, we add it to the final linearization list L = [] + [A] = [A]. After that, class A needs to be removed from all lists in the union. We get L [C] = [C] + [A] + merge ([object], [B, object], [B]).
- Again, take the zero element of the first list - object.
- Let's look it up in all other lists and find that object is the first (not null) element of the list [B, object]. As mentioned above, in essence, this means that the class object is the ancestor of class B. Therefore, at first it makes sense to look for a more specific method in class B. Therefore, the algorithm fairly returns to step 1.
- Again, take the zero element, but this time from the second list, i.e. B from the list [B, object].
- We look for it in other lists and find it only in the third list [B] in the zero position, which suits us perfectly. Therefore, add it to the final list, and then delete from all the lists in the union. We get L = [A] + [B] = [A, B] and accordingly L [C] = [C] + [A, B] + merge ([object], [object]).
- The resulting merge union ([object], [object]) has already been discussed above. As a result, we get L [C] = [C] + [A, B] + [object] = [C] + [A, B, object] = [C, A, B, object]. The list [A, B, object] - this is the result of our merge association (L [A], L [B], [A, B]).
object | D | \ | E | / C
We write the linearization L [C]:
L [C] = [C] + merge (L [D], L [E], [D, E])
L [E] = [E] + merge (L [D], [D])
L [D] = [D] + merge (L [object], [object]) = [D, object]
Let's make the substitutions and get:
L [E] = [E] + merge ([D, object ], [D]) = [E, D, object]
L [C] = [C] + merge ([D, object], [E, D, object], [D, E])
Now look what we got. Merge merging ([D, object], [E, D, object], [D, E]) cannot be completed, because in the lists [D, object] and [D, E], the zero element is D, which is the first list item [E, D, object]. Conversely, E, which is the null element of [E, D, object], is also the first element of [D, E]. Thus, after 3 iterations, the algorithm will come to step 5, after which Python will throw a TypeError error: Cannot create a consistent method resolution order (MRO) for bases D, E. If our union did not end with the list of parents, we would get a violation of the order local seniority: L [C] = [C] + merge ([D, object], [E, D, object]) = [C] + [E] + merge ([D, object], [D, object] ) = [C] + [E, D] + [object] = [C, E, D, object]. With such a linearization of class C, the search would be conducted first in class E,
To solve this problem is not difficult. It is enough to rewrite the declaration in class C (E, D). In this case, we get:
L [C] = [C] + merge ([E, D, object], [D, object], [E, D]) = [C] + [E] + merge ([D , object], [D, object], [D]) = [C] + [E, D, object] = [C, E, D, object].
In fact, nothing has changed, except that in the class declaration, the order of listing the parents is the same as in the linearization of the class, i.e. the order of local seniority is respected. It should be noted that although Python is hinting in what order it would be more logical to indicate the parents, it will not stop you from looking for adventure if you declare your own MRO through a metaclass. But more about that near the end.
Python computes linearization once when creating a class. If you want to get it for self-testing or for some other purposes, use the __mro__ class property (for example, C .__ mro__). To consolidate the material, let’s take a look at the examples that are poorer. The object class is intentionally thrown out so as not to clutter up the linearization. As is known from the above, with single inheritance, classes simply line up from descendant to ancestors, so that the object will always be at the end of any chain. And further. I am not a culinary specialist or a musician, so examples are just examples. You should not focus on semantic inaccuracies in them.
Music
/ \
Rock Gothic ------
/ \ / \
Metal Gothic Rock \
| | \
\ ------------------ Gothic Metal
| /
The 69 eyes
class Music(object): pass
class Rock(Music): pass
class Gothic(Music): pass
class Metal(Rock): pass
class GothicRock(Rock, Gothic): pass
class GothicMetal(Metal, Gothic): pass
class The69Eyes(GothicRock, GothicMetal): pass
L [The69Eyes] = [The69Eyes] + merge (L [GothicRock], L [GothicMetal], [GothicRock, GothicMetal])
L [GothicRock] = [GothicRock] + merge (L [Rock], L [Gothic], [Rock , Gothic])
L [GothicMetal] = [GothicMetal] + merge (L [Metal], L [Gothic], [Metal, Gothic])
L [Rock] = [Rock, Music]
L [Gothic] = [Gothic, Music ]
L [Metal] = [Metal] + [Rock, Music] = [Metal, Rock, Music]
After the substitutions we get:
L [GothicRock] = [GothicRock] + merge ([Rock, Music], [Gothic, Music], [Rock, Gothic]) = [GothicRock, Rock, Gothic, Music]
L [GothicMetal] = [GothicMetal] + merge ([Metal, Rock, Music], [Gothic, Music], [Metal, Gothic]) = [GothicMetal ] + [Metal, Rock, Gothic, Music] = [GothicMetal, Metal, Rock, Gothic, Music]
L [The69Eyes] = [The69Eyes] + merge ([GothicRock, Rock, Gothic, Music], [GothicMetal, Metal, Rock, Gothic, Music], [GothicRock, GothicMetal])
= [The69Eyes] + [GothicRock, GothicMetal] + merge ([Rock, Gothic, Music], [Metal, Rock, Gothic, Music])
= [The69Eyes] + [GothicRock, GothicMetal, Metal] + merge ([Rock, Gothic, Music], [Rock, Gothic, Music] )
= [The69Eyes, GothicRock, GothicMetal, Metal, Rock, Gothic, Music]
Food -------
/ \ \
Meat Milk Flour
| \ \ /
Rabbit Pork Pasty
\ | | /
Pie
class Food(object): pass
class Meat(Food): pass
class Milk(Food): pass
class Flour(Food): pass
class Rabbit(Meat): pass
class Pork(Meat): pass
class Pasty(Milk, Flour): pass
class Pie(Rabbit, Pork, Pasty): pass
L [Pie] = [Pie] + merge (L [Rabbit], L [Pork], L [Pasty], [Rabbit, Pork, Pasty])
L [Rabbit] = [Rabbit] + merge (L [Meat], [Meat])
L [Pork] = [Pork] + merge (L [Meat], [Meat])
L [Pasty] = [Pasty] + merge (L [Milk], L [Flour], [Milk, Flour] )
L [Meat] = [Meat] + merge (L [Food], [Food]) = [Meat, Food]
L [Milk] = [Milk] + merge (L [Food], [Food]) = [Milk , Food]
L [Flour] = [Flour] + merge (L [Food], [Food]) = [Flour, Food]
After the substitutions we get:
L [Rabbit] = [Rabbit, Meat, Food]
L [Pork] = [Pork, Meat, Food]
L [Pasty] = [Pasty] + merge ([Milk, Food], [Flour, Food], [Milk, Flour]) = [Pasty] + [Milk, Flour, Food] = [ Pasty, Milk, Flour, Food]
L [Pie] = [Pie] + merge ([Rabbit, Meat, Food], [Pork, Meat, Food], [Pasty, Milk, Flour, Food], [Rabbit, Pork, Pasty])
= [Pie] + [Rabbit] + merge ([Meat, Food], [Pork, Meat, Food], [Pasty, Milk, Flour, Food], [Pork, Pasty])
= [Pie] + [Rabbit, Pork] + merge ([ Meat, Food], [Meat, Food], [Pasty, Milk, Flour, Food], [Pasty])
= [Pie] + [Rabbit, Pork, Meat] + merge ([Food], [Food], [Pasty , Milk, Flour, Food], [Pasty])
= [Pie] + [Rabbit, Pork, Meat, Pasty] + merge ([Food], [Food], [Milk, Flour, Food])
= [Pie] + [Rabbit, Pork, Meat, Pasty, Milk, Flour, Food]
= [Pie, Rabbit, Pork, Meat, Pasty, Milk, Flour, Food]
How to contact the ancestors.
Multiple inheritance poses another specific problem. Actually, a direct search for some method in the parent classes is only part of the benefits that can be derived from it. As in the case of single inheritance, you can often make your life easier by implementing a method in a descendant that, in addition to some actions, will call the same parent method. For example, you can often find this: However, for the case of multiple inheritance, this approach is not suitable. And for what reasons:
class B(A):
def __init__(self):
# something
A.__init__(self)
class C(B, A):
def __init__(self):
# something
B.__init__(self)
A.__init__(self)
First, we explicitly refer to the parent classes (in fact, the same is true in the case of single inheritance). If we want to replace one of our ancestors with another class or remove it altogether, then we will have to change all the functions that accessed it. This is fraught with bugs if we miss something. But this is still half the trouble. Secondly, we do not know anything about classes A and B. Perhaps they have common ancestors, which they refer to in the same way: If so, then it turns out that the initialization of the common ancestors will work twice. It is not right. To avoid this, Python has a super class. In version 3.0, he is finally humanized and can be accessed as follows:
class A(P1, P2):
def __init__(self):
# something
P1.__init__(self)
P2.__init__(self)
class B(P1, P2):
def __init__(self):
# something
P1.__init__(self)
P2.__init__(self)
class C(B, A):
def __init__(self):
# something
super().__init__() # для версий младше 3.0 нужно использовать super(C, self)
Note that in versions 2.x, the first argument must specify the class itself, and not any of its parent. In fact, the super class object remembers the arguments passed to it at the time of initialization and, when calling any method (super () .__ init __ (self) in the example above) goes through the linearization list of the second argument class (self .__ class __.__ mro__), trying to call this method in turn for all classes following the class in the first argument (class C), passing the first argument (self) as a parameter. Those. for our case:
self .__ class __.__ mro__ = [C, B, A, P1, P2, ...]
super (C, self) .__ init __ () => B .__ init __ (self)
super (B, self) .__ init __ ( ) => A .__ init __ (self)
super (A, self) .__ init __ () => P1 .__ init __ (self)
As you can see, from the B .__ init__ method, when using super, the A .__ init__ method will be called, although the class A has nothing to do with it and is not its ancestor. In this case, if necessary, the chain will work out the methods of all ancestors once.
Thanks to this approach, you can, for example, introduce the allergen method for all components for the examined pie example, which will consistently go through the chain of ancestors to make a list of all allergen components in order to warn buyers. It will be convenient instead of rewriting the “not recommended” list for each product just to inherit it from its constituent components. Then the list will be generated automatically. Similarly, it will be possible to offer the user a choice of drinks for each product, or to tweak the weight of the user's preferences on a self-made Internet radio station, going from a specific group to genres with a certain attenuation coefficient.
An example with a pie might look like this (for version 2.x): As a result, we will see the following:
class Food(object):
def drink(self):
return ['Water', 'Cola']
def allergen(self):
return []
class Meat(Food):
def drink(self):
return ['Red wine'] + super(Meat, self).drink()
class Milk(Food):
def allergen(self):
return ['Milk-protein'] + super(Milk, self).allergen()
class Flour(Food): pass
class Rabbit(Meat):
def drink(self):
return ['Novello wine'] + super(Rabbit, self).drink()
class Pork(Meat):
def drink(self):
return ['Sovinion wine'] + super(Pork, self).drink()
def allergen(self):
return ['Pork-protein'] + super(Pork, self).allergen()
class Pasty(Milk, Flour): pass
class Pie(Rabbit, Pork, Pasty):
def drink(self):
return ['Mineral water'] + super(Pie, self).drink()
if __name__ == "__main__":
pie = Pie()
print 'List of allergens: '
for allergen in pie.allergen(): print ' - ' + allergen
print 'List of recommended drinks: '
for drink in pie.drink(): print ' - ' + drink
List of allergens:
- Pork-protein
- Milk-protein
List of recommended drinks:
- Mineral water
- Novello wine
- Sovinion wine
- Red wine
- Water
- Cola
Based on this list, you can understand how the linearization list was handled. As you can see, none of the parent methods was called twice, otherwise repetitions would be found in the list of allergens or recommendations. In addition, note that in the oldest Food class, both methods are defined - allergen and drink. The super () call does not perform any checks, so if we try to call a non-existent method, we get an error like AttributeError: 'super' object has no attribute 'allergen'.
When linearization cannot be compiled.
The case has already been analyzed above when it was impossible to compose a linearization using the C3 algorithm. However, then the problem was solved by changing the places of the ancestor classes in the declaration of the descendant class. There are other cases in which the linearization is not possible: L [E] = [E] + merge (L [C], L [D], [C, D]) = [E] + merge ([C, A , B], [D, B, A], [C, D]) = [E] + [C, D] + merge ([A, B], [B, A])
class C(A, B): pass
class D(B, A): pass
class E(C, D): pass
As you can see, the conflict turned out to be unsolvable, because in the declaration C the class A is before B, and in the declaration D it is vice versa. Well, from this place you have to go and review the structure. But if you really need to get a quick fast or you just know what you are doing, Python will not limit you. You can define your own linearization through metaclasses. To do this, it is enough to specify the mro (cls) method in the metaclass - in fact, redefine the method of the base metaclass type, which will return the linearization you need. Further, the class declaration differs for version 3.0 and 2.x:
class MetaMRO(type):
def mro(cls):
return (cls, A, B, C, D object)
class E(C, D): __metaclass__ = MetaMRO # 2.x
class E(C, D, metaclass = MetaMRO): pass # 3.0
After that, E .__ mro__ = [E, A, B, C, D, object]. Note that if you take responsibility for the MRO, Python does not conduct any additional checks and you can safely search the ancestors earlier than the descendants. And although this is not a desirable practice, but it is possible.
Useful links:
Unifying types and classes in Python 2.2 - about the separation of the object model and the meta-data model. It also discusses MRO, multiple inheritance issues, and super ().
The Python 2.3 Method Resolution Order - C3 algorithm with examples. At the end there is an implementation of the mro and merge functions on pure Python for those who better perceive the code than the text.
A Monotonic Superclass Linearization for Dylan - Comparison of some types of linearization.
Afterword.
Of course, it is impossible to cover all related topics, and perhaps someone has more questions than answers. For example, what are metaclasses, base classes of type and object, and the like. If there is interest, then, over time, I could try to parse such topics:
- introspection in Python: interactive help, dir, sys, etc.
- type and object: most likely as a free and abbreviated translation of this
- magic in Python: __str__, __init__, __new__, __slots__, etc. In fact, there are quite a lot of it, so it can turn out several parts.
- metaclasses.
PS: Thanks to all those who helped me post this topic and personally Goodrone .