Friday, December 27, 2019

Python MRO (Method Resolution Order)

The python MRO defines the class search path used by Python to search for the right method to use in classe having multi-inheritance. Python supports class inheriting from other classes, the class being inheritated is called PARENT or SUPER class, while the class that inherits is called CHILD or SUB class. In python method resolution order defines the order in which the base classes are searched when executing a method. This order is also called LINEARIZATION of a class and set of rules are called MRO(Method Resolution Order).

For Example:


class A:
    def callme(self):
        print("From class A")

class B(A):
    def callme(self):
        print("From class B")

class C(A, B):
    def callme(self):
        print("From class C")

c = C()
c.callme()

As shown in above example when "callme" method executed on class C instance Python MRO decides which methods to be executed.
What is solution to the above problem ?
Solution to above problem is Two Algorithms to find Method Resolution Order.

                    Solution
                       |
                       |
                 Two Algorithms
                       |
                      / \
                    /     \
                  /         \
              Old MRO    New MRO (C3 Algorithm)
                 |           |
            Old Classes  New Classes

Old Class and New Class Example:

Old Classes:
  • Doesn't inherit from python root object class.
  • Uses old python MRO algorithm (DLR)

class A:
    def callme(self):
        pass

New Classes
  • First Parent inherit from python root object class.
  • Uses new python MRo algorithm (C3).
  • Introduced in python 2.3
class A(object):
    def callme(self):
        pass

History of Python MRO


Everything started in October 2002 with a post by Samuele Pedroni to the Python development mailing list. In his post, Samuele showed that the Python 2.2 method resolution order is not monotonic and he proposed to replace it with the C3 method resolution order. Guido agreed with his arguments and therefore now Python 2.3 uses C3. The C3 method itself has nothing to do with Python, since it was invented by people working on Dylan and it is described in a paper intended for lispers. The present paper gives a (hopefully) readable discussion of the C3 algorithm for Pythonistas who want to understand the reasons for the change.
  • Here is the link with detailed explaination of MRO introduced in python 2.3.
  • Here is the link to Samuele Pedroni's email to python mailing list.

What is Old MRO algorithm ?

Python old mro uses DLR algorithm i.e. Depth First, Left to Right. During implementing multiple inheritances, Python builds a list of classes to search as it needs to resolve which method has to be called when one is invoked by an instance. As the name suggests, the method resolution order will search the depth-first, then go left to right.

class A:
    pass

class B:
    pass

class C(A, B):
    pass

class D(B, A):
    pass

class E(C,D):
    pass

In the above Example algorithm first looks into the instance class for the invoked method. If not present, then it looks into the first parent, if that too is not present then-parent of the parent is looked into. This continues till the end of the depth of class and finally, till the end of inherited classes. So, the resolution order in our last example will be D, B, A, C, A. But, A cannot be twice present thus, the order will be D, B, A, C. But this algorithm varying in different ways and showing different behaviours at different times.

So, why Python search for A before C when A does not inherits from object in Python 2 ? This is due to the old classes MRO algorithm behaviour. It is a very simple and easy to understand algorithm : When a class inherits from multiple parents, Python build a list of classes to search for when it needs to resolve which method has to be called when one in invoked by an instance. This algorithm is a tree routing, and works this way, deep first, from left to right :
  1. Look if method exists in instance class
  2. If not, looks if it exists in its first parent, then in the parent of the parent and so on
  3. If not, it looks if current class inherits from others classes up to the current instance others parents.
So in our example, algorithm search path is : D, B, A, C, A. A class cannot appears twice in search path, so the final version is D, B, A, C:
Looking in D If not found, looking in B If not found, looking un B first parent A If not found, going back in B others parents (none) If not found, looking in D others parents : C

What is New MRO algorithm ?


C3 Linearization algorithm is an algorithm that uses new-style classes. It is used to remove an inconsistency created by DLR Algorithm. It has certain limitation they are: Children precede their parents. If a class inherits from multiple classes, they are kept in the order specified in the tuple of the base class.

C3 Linearization Algorithm works on three rules: Inheritance graph determines the structure of method resolution order. User have to visit the super class only after the method of the local classes are visited. Monotonicity.

As shown in example of new classes, when the class inherits from Python root object the behaviour changes. If you run the above using python3 the algorithm behaviour change too. This is because in Python 3 or in Python 2 using object as a parent class the new MRO algorithm is used.
So, what happens if we run above example using python 3 ?


class A(object):
    pass

class B(object):
    pass

class C(A, B):
    pass

class D(B, A):
    pass

class E(C,D):
    pass

TypeError: Error when calling the metaclass bases Cannot create a consistent method resolution order (MRO) for bases A, B

You will see above error when you run above code with python 3. Python 3 MRO algorithm is not able to find proper method resolution for above inherited classes so it breaks and throws typeerror related to mro.
Lets modify above code to work with python 3 and find out what is mro for above code.


class A(object):
    pass

class B(object):
    pass

class C(A, B):
    pass

class D(A, B):
    pass

class E(C,D):
    pass

E.__mro__

(<class '__main__.E'>, <class '__main__.C'>, <class '__main__.D'>, <class '__main__.A'>, <class '__main__.B'>, <type 'object'>)


As shown in above output MRO for given code is E, C, D, A, B using new c3 linerization algorithm.

References

at

No comments:

Post a Comment