{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# The curious case of `__mro__`\n", "## Method resolution order in multiple inheritance using C3 linearization\n", "" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true, "slideshow": { "slide_type": "slide" } }, "source": [ "# Inheritance in Python\n", "\n", "* Python supports **multiple inheritance**, i.e. a class can be derived from more than one base classes\n", "* In multiple inheritance, the features of all the base classes are inherited into the derived class\n", "* The syntax for multiple inheritance is similar to single inheritance" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false, "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(, )\n" ] } ], "source": [ "class A:\n", " pass\n", "\n", "class B:\n", " pass\n", "\n", "class C(A,B):\n", " pass\n", "\n", "print(C.__bases__)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# What is MRO?\n", "* MRO stands for Method Resolution Order\n", "* MRO is the order in which base classes in the inheritance hierarchy are searched when looking for a method\n", "* All Python versions after 2.3 use the *C3 linearization* algorithm to determine this order\n", "* Not all classes admit a linearization. There are cases, in complicated hierarchies, where it is not possible to derive a class such that its linearization respects all the desired properties.\n", "\n", "Check [this article](https://www.python.org/download/releases/2.3/mro/) on python.org for more info. Part of this presentation also based on [this tutorial](https://www.youtube.com/watch?v=YLgf8wGCX2w)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Why is this useful?\n", "\n", "* Given a class `C`, in the case of single inheritance hierarchy, if `C` is a subclass of `C1`, and `C1` is a subclass of `C2`, then the linearization of `C` is simply the list `[C,C1,C2]`.\n", "* However, in a complicated multiple inheritance hierarchy, it is a non-trivial task to specify the order in which methods are overridden, i.e. to specify the order of the ancestors of `C`.\n", "* We need to be able discover **deterministically** the order of classes for method calls in the inheritance chain.\n", "* The list of the ancestors of a class `C`, including the class itself, ordered from the nearest ancestor to the furthest, is called the *class precedence list* or the *linearization* of `C`.\n", "* The Method Resolution Order (MRO) is the set of rules that construct the linearization. In the Python literature, the idiom the *MRO* of the class `C` is also used as a synonymous for the *linearization* of `C`." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# The diamond problem\n", "\n", "* In the above example the `Button` class inherits two differerent implementations of `equals()`\n", "* It has no implementation of the operation of its own\n", "* When `button.equals()` is called, it is unknown which implemetation - from `Rectangle`, `Clickable` or `object` will be used" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# C3 Linearization\n", "* First introduced in the Dylan language\n", "* Algorithm based on 3 important properties (this is how the name *C3* is derived)\n", " 1. Consistent extended precedence graph (MRO is determined based on structure of the inheritance graph)\n", " 2. Preserving local precedence ordering (no class will appear before any of its subclasses)\n", " 3. Monotonicity" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Monotonicity\n", "* An MRO is monotonic when the following is true:\n", " - If `C1` precedes `C2` in the linearization of `C` then `C1` precedes `C2` in the linearization of any subclass of `C`.\n", "* Consider: `class X(O), class Y(O), class A(X,Y), class B(Y,X), class C(B,A)`\n", " - Based on monotonicity it is **not** possible to derive a new class `C` from `A` and `B` since `X` precedes `Y` in `A`, but `Y` precedes `X` in `B`, therefore the method resolution order would be ambiguous in `C` (`XY` breaks monotonicity with `B`, `YX` breaks monotonicity with `A`).\n", "" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true, "slideshow": { "slide_type": "slide" } }, "source": [ "# Definition and notation\n", "* Notation\n", " - `C1 C2 ... CN` indicates the list of classes `[C1,C2,...,CN]`\n", " - The *head* of the list is its first element: head = `C1`\n", " - The *tail* is the rest of the list: tail = `C2 ... CN`\n", " - The sum of the lists `[C] + [C1,C2,...,CN] = C + (C1 C2 ... CN) = C C1 C2 ... CN`\n", "* Consider a class `C` in a multiple inheritance hierarchy, with `C` inheriting from the base classes `B1, B2, ..., BN`:\n", " - The linearization of `C` is the sum of `C` plus the merge of linearizations of the parents and the list of the parents\n", " - `L[C(B1 ... BN)] = C + merge(L[B1],...,L[BN], B1 ... BN)`\n", "* Example: `L[Y(X1 X2 X3)] = Y + merge(L[X1],L[X2],L[X3], X1 X2 X3)`\n", " " ] }, { "cell_type": "markdown", "metadata": { "collapsed": true, "slideshow": { "slide_type": "slide" } }, "source": [ "# Computing merge\n", "Consider a simple merge example: `merge(DO,EO,DE) = DEO`\n", "1. Select the first head of the lists which does not appear in the tail of any of the other lists.\n", " - A good head may appear as the first element in multiple lists at the same time, but it is forbidden to appear anywhere else.\n", "2. Remove the selected element from all the lists where it appears as a head and append to the output list.\n", "3. Repeat the operation of selecting and removing a good head to extend the output list until all remaining lists are exhausted.\n", "4. If at some point no good head can be selected, because the heads of all remaining lists appear in any one tail of the lists, then the merge is impossible to compute due to cyclic dependencies in the inheritance hierarchy and no linearization of the original class exists.\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Properties of merge\n", "* Three important considerations when computing merge:\n", " 1. The merge of several sequences is a sequence that contains **each** of the the elements of the input sequence\n", " - All elements within the input lists *DO*, *EO* and *DE* are present in the merged result *DEO*.\n", " 2. An element that appears in more than once of the input sequences appears **only once** in the output sequence\n", " - *D*, *E* and *O* appear in more than on input sequence, but the result has only one instance of each.\n", " 3. If two elements appear in the same input sequence, their order in the output sequence is the same as their order in the input sequence.\n", " - In the input sequence, D precedes both O and E; E precedes O. The same ordering is maintained in the merged output." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Compute the linearization:\n", "`class A(B,C), class B(D,E) class C(D,F), class D(O), class E(O), class F(O), class O`\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# C3 computing example\n", "**`L[C(B1 ... BN)] = C + merge(L[B1],...,L[BN], B1 ... BN)`** \n", "```\n", "L[O] = O\n", "L[D] = D + merge(L[O],O) = D + merge(O,O) = DO\n", "L[E] = EO, L[F] = FO \n", "L[B] = B + merge(L[D],L[E],DE) \n", " = B + merge(DO,EO,DE)\n", " = B + D + merge(O,EO,E)\n", " = B + D + E + merge(O,O)\n", " = BDEO\n", "L[C] = C + merge(L[D],L[F],DF)\n", " = C + merge(DO,FO,DF)\n", " = CDFO\n", "L[A] = A + merge(L[B],L[C],BC)\n", " = A + merge(BDEO,CDFO,BC)\n", " = A + B + merge(DEO,CDFO,C)\n", " = A + B + C + merge(DEO,DFO)\n", " = A + B + C + D + merge(EO,FO)\n", " = A + B + C + D + E + merge(O,FO)\n", " = A + B + C + D + E + F + merge(O,O)\n", " = ABCDEFO\n", "```" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(, , , , , , )\n", "(, , , , , , )\n" ] } ], "source": [ "class F: pass\n", "class E: pass\n", "class D: pass\n", "class C(D,F): pass\n", "class B(D,E): pass\n", "class A(B,C): pass\n", "\n", "from inspect import getmro\n", "print(getmro(A))\n", "print(A.__mro__)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "ename": "TypeError", "evalue": "Cannot create a consistent method resolution\norder (MRO) for bases B, A", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[1;32mclass\u001b[0m \u001b[0mC\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mA\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mB\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m \u001b[1;32mpass\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m 4\u001b[0m \u001b[1;32mclass\u001b[0m \u001b[0mD\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mB\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mA\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m \u001b[1;32mpass\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m \u001b[1;32mclass\u001b[0m \u001b[0mE\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mC\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mD\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m \u001b[1;32mpass\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 6\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m 7\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mE\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m__mro__\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[0;31mTypeError\u001b[0m: Cannot create a consistent method resolution\norder (MRO) for bases B, A" ] } ], "source": [ "class A: pass\n", "class B: pass\n", "class C(A,B): pass\n", "class D(B,A): pass\n", "class E(C,D): pass\n", "\n", "print(E.__mro__)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "" ] } ], "metadata": { "celltoolbar": "Slideshow", "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.2" } }, "nbformat": 4, "nbformat_minor": 1 }