Item 25: Inconsistent method resolution order

[PeterDrake]

p. 71 describes MRO as "depth-first, left-to-right", but the example on p. 72 is breadth-first.

According to

http://docstore.mik.ua/orelly/other/python/0596001886_pythonian-chp-5-sect-2.html#pythonian-CHP-5-FIG-1

the former is "classic" and the latter is "new-style".

On a closely related note, in the paragraph after the last block of code on p. 72, it doesn't seem accurate to say that TimesFiveCorrect.__init__ calls PlusTwoCorrect.__init__; that's just the order in which those initializers are run.

[bslatkin]

Thanks for the report.

You said:

p. 71 describes MRO as "depth-first, left-to-right", but the example on p. 72 is breadth-first... According to [a link] the former is "classic" and the latter is "new-style".

The text from the book says:

To solve these problems, Python 2.2 added the super built-in function and defined the method resolution order (MRO). The MRO standardizes which superclasses are initialized before others (e.g., depth-first, left-to-right). It also ensures that common superclasses in diamond hierarchies are only run once.

I think the primary confusion here is the text reads like I'm saying that the MRO is "depth-first, left-to-right". But that's just an example of one possible ordering. That's why I used "e.g.,". The only things that are important here are 1) that there's a standardized ordering, and 2) that superclasses are only initialized once.

If you look at the Python 2.2 release notes, it describes the "classic" MRO style as "left-to-right depth-first rule". It describes the "new-style" MRO as:

We use this observation to explain our new lookup rule. Using the classic lookup rule, construct the list of classes that would be searched, including duplicates. Now for each class that occurs in the list multiple times, remove all occurrences except for the last. The resulting list contains each ancestor class exactly once (including the most derived class, D in the example): D, B, C, A.

It's essentially the same algorithm as classic with earlier duplicates removed. However, the 2.2.2 release notes also acknowledge that the original method resolution order introduced in Python 2.2 was wrong. In Python 2.3 the MRO was updated to use C3 linearization. The details are described in detail here.

When writing the book I decided that C3 linearization is a complicated detail of very little practical value. I left it out. I think I should just remove the text "(e.g., depth-first, left-to-right)" from the book so I don't introduce any confusion. Does that sound right to you?

---

Otherwise: I split off your second question in #41

[bslatkin]

Here's another example of someone being confused about this. It's in Japanese but the translation reads:

Here, the "depth-first, left-to-right," but there is a, become a story that is different from, was examined MRO is called C3 linearization algorithm seems defined in.

C3 linearization - Wikipedia, the free encyclopedia

That is,

(For example, depth-first, left-to-right) Description that is really a parable, algorithm I have decided to unique, is that not only talking about that.

That last sentence seems to identify that the "e.g." was just an example of a possible ordering, not the actual ordering used by Python. But it seems like they were still confused by the book so I should change it.

[PeterDrake]

Yes, I think the simplest fix is removing "(e.g., depth-first, left-to-right)". You might mention "C3 linearization" so that interested readers could look up the details.

The example on the Wikipedia page for C3 linearization happens to reach the same result as a breadth-first traversal. It seems conceivable to me that there are cases where these two algorithms are not the same, perhaps in a case where some paths to the base class are longer or wider than others. It's certainly complicated enough to leave out of a book like this (and probably enough to avoid multiple inheritance in practice).

On Wed, Jun 1, 2016 at 8:48 PM, Brett Slatkin notifications@github.com wrote:

Thanks for the report.

You said:

p. 71 describes MRO as "depth-first, left-to-right", but the example on p. 72 is breadth-first... According to [a link] the former is "classic" and the latter is "new-style".

The text from the book says:

To solve these problems, Python 2.2 added the super built-in function and defined the method resolution order (MRO). The MRO standardizes which superclasses are initialized before others (e.g., depth-first, left-to-right). It also ensures that common superclasses in diamond hierarchies are only run once.

I think the primary confusion here is the text reads like I'm saying that the MRO is "depth-first, left-to-right". But that's just an example of one possible ordering. That's why I used "e.g.,". The only things that are important here are 1) that there's a standardized ordering, and 2) that superclasses are only initialized once.

If you look at the Python 2.2 release notes https://www.python.org/download/releases/2.2/descrintro/#mro, it describes the "classic" MRO style as "left-to-right depth-first rule". It describes the "new-style" MRO as:

We use this observation to explain our new lookup rule. Using the classic lookup rule, construct the list of classes that would be searched, including duplicates. Now for each class that occurs in the list multiple times, remove all occurrences except for the last. The resulting list contains each ancestor class exactly once (including the most derived class, D in the example): D, B, C, A.

It's essentially the same algorithm as classic with earlier duplicates removed. However, the 2.2.2 release notes also acknowledge that the original method resolution order introduced in Python 2.2 was wrong. In Python 2.3 the MRO was updated to use C3 linearization https://en.wikipedia.org/wiki/C3_linearization. The details are described in detail here https://www.python.org/download/releases/2.3/mro/.

When writing the book I decided that C3 linearization is a complicated detail of very little practical value. I left it out. I think I should just remove the text "(e.g., depth-first, left-to-right)" from the book so I

don't introduce any confusion. Does that sound right to you?

Otherwise: I split off your second question in #41 https://github.com/bslatkin/effectivepython/issues/41

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/bslatkin/effectivepython/issues/40#issuecomment-223188611, or mute the thread https://github.com/notifications/unsubscribe/AA2RaU-fUFQ93XRSfosP8PklxhXzN3ybks5qHlJ_gaJpZM4ILKBk .

Peter Drake http://www.lclark.edu/~drake

[bslatkin]

This will be fixed in a future release. Thanks!