In
http://mail.python.org/pipermail/python-dev/2002-October/029035.html
and following messages, Samuele Pedroni argues that the
current MRO algorithm has some unexpected properties,
and that the "naive" algorithm described in the docs
(keep the last occurrence in a depth-first search) is
not monotonic. The current algorithm is monotonic. A
better algorithm, named C3, is described in this paper:
http://www.webcom.com/haahr/dylan/linearization-oopsla96.html
I believe that the current algorithm is the same as
L*[LOOPS] mentioned in this paper (though I have no
proof). The paper argues convincingly that C3 is better
than L*[LOOPS], so I propose to use C3 starting in
Python 2.3.
This can cause backwards compatibilities in certain
cases, but the new algorithm matches intuition better
than the current algorithm. (The naive algorithm from
the docs is unacceptable due to its non-monotonicity.)
|