[Python-bugs-list] [ python-Bugs-618704 ] Use C3 MRO algorithm

noreply@sourceforge.net noreply@sourceforge.net
Thu, 14 Nov 2002 11:50:56 -0800


Bugs item #618704, was opened at 2002-10-04 15:11
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=618704&group_id=5470

Category: Type/class unification
Group: Python 2.3
>Status: Closed
>Resolution: Fixed
Priority: 5
Submitted By: Guido van Rossum (gvanrossum)
Assigned to: Guido van Rossum (gvanrossum)
Summary: Use C3 MRO algorithm

Initial Comment:
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.)

----------------------------------------------------------------------

>Comment By: Guido van Rossum (gvanrossum)
Date: 2002-11-14 14:50

Message:
Logged In: YES 
user_id=6380

Fixed; I checked in the code from patch 619475.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=618704&group_id=5470