Python's method-resolution algorithm: An implementation question

Evan Aad oddeveneven at gmail.com
Tue Aug 15 11:56:27 EDT 2017


According to the description of Python's method resolution order (mro)
(https://www.python.org/download/releases/2.3/mro/), a.k.a. C3
linearization (see Wikipedia), the algorithm can be described as
follows:

"the linearization of C is the sum of C plus the merge of the
linearizations of the parents and the list of the parents."

Symbolically, the algorithm is defined recursively thus:

L(O) = <O>
L(C) = <C> + merge(L(B1),..., L(Bn), <B1,...,Bn>)

where

* O is the class from which every class inherits.
* C is a class that inherits directly from B1, ..., Bn, in this order.
* < and > are list delimiters.
* + is the list-concatenation operator.
* 'merge' merges its list arguments into a single list with no
repetitions in the manner described in the next paragraph.

Consider the head of the first list, i.e L(B1)[0]: if it is a good
head, i.e. if it is not in the proper tail of any of the other lists,
add it to the linearization of C, and remove it from all the lists in
the merge. Otherwise, consider the head of the next list, etc. Repeat
until no more classes, or no good heads. In the latter case, it is
impossible to construct the merge.



Why is the list <B1,...,Bn> of parents given as an argument to
'merge'? Will the algorithm produce different results if this argument
is omitted?



More information about the Python-list mailing list