Use the C3 method resolution order in multiple inheritance

Perl 5.10 introduced a flexible method resolution order mechanism. Instead of Perl’s default order (see Understand Perl’s default inheritance model), you can try something less stupid by using the mro pragma to specify which order perl.

So far, there are only two resolution orders: dfs, which is Perl’s default depth-first search, and c3, a new resolution order that handles some problems in multiple inheritance.

Regular readers of this blog may have heard this before, but for the safety of the passengers around you, please give us a couple of minutes where you’re not distracted by other attentions: DON’T USE MULTIPLE INHERITANCE IF YOU CAN DO IT ANY OTHER WAY. It causes global warmingclimate change by generating tons of carbon and nitrogen. That’s the short story. The next time we have to write that, we’re using the <BLINK> tag.

So, you’ve decided to harm the planet. Maybe you have a good reason for that. You have an inheritance relationship that looks like a V:

In Perl’s default method resolution, it searches in the order (F, B, A, Y, X). However, what if the leftmost immediate parent class B doesn’t implement the method, but the rightmost immediate parent class Y does? Do you want it to search through all of the leftmost branch, perhaps skipping Y altogether?

The C3 method resolution order is a scheme such that perl searches any child class that might implement a method before it searches a parent class. That is, it’s almost like looking for breadth instead of depth, although it’s a bit more complicated than that. The full details of the idea are in A Monotonic Superclass Linearization for Dylan, the 1996 paper that introduced the idea. The name C3 refers to class C that uses the three properties presented in the paper which we won’t spend space on here.

Before you think about C3, though, look at the mro pragma, which first came with Perl 5.10. It has a subroutine, get_linear_isa, that can tell you what the particular @ISA traversal will be:

use 5.014;

use mro; # just to get get_linear_isa

package A { 1; }
package B { our @ISA = 'A' }

package X { 1; }
package Y { our @ISA = 'X' }

package F { our @ISA = qw(B Y) }

say "resolution order is @{ mro::get_linear_isa( 'F' ) }";

This uses Perl’s default resolution order (dfs), so you get what you expect, the left-first, depth-first traversal:

resolution order is F B A Y X

And, if you change the @ISA in F to switch the order so the X-Y branch is on the left, you get a different order:

use 5.014;

use mro; # just to get get_linear_isa

...; # same as before

package F { our @ISA = qw(Y B) } # now the other way around

say "resolution order is @{ mro::get_linear_isa( 'F' ) }";

Now the other branch shows up first, but still with its depth-first progression:

resolution order is F Y X B A

That’s still not much of a problem. What happens, however, if you have a situation where you have an inheritance structure so that you might end up in the same class through different paths, also know as diamond inheritance or cyclic inheritance? What if you have this situation (which you should try to avoid because it wrecks the planet):

That changes the Perl implementation to have another level of inheritance:

use 5.014;

use mro;

package O { 1; }

package A { our @ISA = 'O' }
package B { our @ISA = 'A' }

package X { our @ISA = 'O' }
package Y { our @ISA = 'X' }

package F { our @ISA = qw(B Y) } # now the other way around

say "resolution order is @{ mro::get_linear_isa( 'F' ) }";

Now the resolution order travels up through B and A to get to O, getting whatever version of the method that O implements:

resolution order is F B A O Y X

But, in this case, if neither B nor A made a change to the method, maybe they don’t care about that method. However, maybe Y does care and has a different implementation method. Perl’s default search never finds the overridden or extended version in Y because it makes it to O first. The C3 algorithm is designed to address that sort of problem.

Before you change around the code in a lot of classes, you can use mro to look at the what a different order might do by giving get_linear_isa the resolution order that you want to use. In this case, you can use the only other resolution order that mro provides:

use 5.014;

use mro;

package O { 1; }

package A { our @ISA = 'O' }
package B { our @ISA = 'A' }

package X { our @ISA = 'O' }
package Y { our @ISA = 'X' }

package F { our @ISA = qw(Y B) } # now the other way around

say "resolution order is @{ mro::get_linear_isa( 'F', 'c3' ) }";

Even though you haven’t changed the code in the classes, you get to see what the resolution order would be. Now O is last class in the list, so perl searches for any specialization of O before it reaches O:

resolution order is F Y X B A O

Why would you ever have that sort of problem? Remembering our warning to you, consider various windowing frameworks that use inheritance from many sources to cobble together the composed widget you’d like to have (these are the examples in the original Dylan paper). Suppose you have a widget, that you are required by the framework to inherit from Object for all widgets, and then you have to mix-in the various features that you want. You can blame your framework for this mess:

In Perl code, that looks like:

use 5.014;

use mro;

package Object { 1; }

package ChoiceWidget { our @ISA = 'Object' }
package PopupMixin   { our @ISA = 'Object' }

package Menu         { our @ISA = 'ChoiceWidget' }

package PopupMenu { 
	our @ISA = qw(Menu PopupMixin) 
	}

say "Traditional resolution order is
	@{ mro::get_linear_isa( 'PopupMenu', 'dfs' ) }";

say "C3 resolution order is
	@{ mro::get_linear_isa( 'PopupMenu', 'c3' ) }";

The result of the two resolutions orders are as you saw before, where the default order would skip the PopupMixin subclass, but the C3 order will put it before Object:

Traditional resolution order is
	PopupMenu Menu ChoiceWidget Object PopupMixin
C3 resolution order is
	PopupMenu Menu ChoiceWidget PopupMixin Object

This doesn’t mean that C3 can solve all of your problems. Consider this other mess of inheritance from the Dylan paper:

In Perl, that looks like:

use 5.014;

use mro;

package Pane { 1; }

package ScrollingMixin { 1; }
package EditingMixin   { 1; }

package ScrollablePane { our @ISA = qw(Pane ScrollingMixin) }
package EditablePane   { our @ISA = qw(Pane EditingMixin) }

package ScrollableEditablePane { 
	our @ISA = qw(ScrollablePane EditablePane) 
	} # now the other way around

say "Traditional resolution order is
	@{ mro::get_linear_isa( 'ScrollableEditablePane', 'dfs' ) }";

say "C3 resolution order is
	@{ mro::get_linear_isa( 'ScrollableEditablePane', 'c3' ) }";

Perl’s C3 works in this case where it doesn’t in the original Dylan example. Here the resolution order is trying the scrolling parts first both for the parts that inherit from Pane and the mixins:

Traditional resolution order is
	ScrollableEditablePane ScrollablePane Pane ScrollingMixin EditablePane EditingMixin
C3 resolution order is
	ScrollableEditablePane ScrollablePane EditablePane Pane ScrollingMixin EditingMixin

If you don’t like any of these orders, the mro mechanism lets you create other sorts of method resolution orders if you don’t like the ones that you find. You’ll probably have an easier time fixing the design, though, so try that first.

Things to remember

  • The mro pragma lets you change the order that Perl uses to find a method.
  • Use the C3 method resolution order to check all child classes before any parent classes.
  • C3 can’t solve every inheritance mess.
Leave a comment

0 Comments.

Leave a Reply


[ Ctrl + Enter ]

7ads6x98y