[PDD15 PROPOSAL] Pluggable MRO

0 views
Skip to first unread message

Jonathan Worthington

unread,
Mar 10, 2007, 11:51:28 AM3/10/07
to perl6-i...@perl.org
Hi,

One of the things we need to specify in PDD 15 is method resolution order.

--
BACKGROUND
The MRO, short for Method Resolution Order, is the order in which we
search classes in an inheritance hierarchy when looking for attributes
or methods to call. The MRO is represented as a linearization of the
hierarchy - basically, a list of classes in the order that we should
search them when looking for an attribute or method.

THE NEED FOR PLUGABILITY
Different languages may have a different MRO. Python since 2.3 and Perl
6 by default use C3. Perl 5 used something else. Therefore, we need
computation of the MRO to be pluggable.

It's clear that we need to have MRO pluggable by class, since classes
will be written in many languages. More interesting is that, for Perl 6,
we also need to override the MRO on a by-method-call basis - you can
change the dispatch order at the call site! While in Perl 6 attributes
are not an issue in this (since they are private to a class and only
have public accessors which are methods), for completeness we may want a
way to specify the MRO for an individual attribute lookup too.

BEING PLUGGABLE IS EASY!
Through the MetaClass of any class, you can get a list of its immediate
parents by calling the parent method, and so on up the tree. This means
that computation of the MRO can be completely abstracted away from the
internals of the class/object system. It also means there's no reason at
all why a PIR sub cannot be called to compute an MRO.

Obviously, for performance reasons we should implement computation of
some of the most common MROs directly inside Parrot, but those also
should only work through the parents method available in the MetaClass PMC.

CLASS MRO
The MetaClass PMc should get two extra fields:

* MRO type - a value from an enum like...
0 - C3
1 - Custom
2 - Preorder

* If MRO type is 1 (Custom), a reference to a Sub PMC to compute the MRO.

We compute the MRO at the time when the class is first instantiated
(rather than upon the addition of a parent) - note that adding a new
parent to an already instantiated class will clone the class, name
binding the new modified class to the name of the original class, but
not affecting any existing instances of the class.

Additionally, the MetaClass PMC will get an additional method for
setting the MRO. Optionally, we could allow a language to specify its
own default.

METHOD CALL MRO
Normal method discovery using the MRO of the class will be implemented
inside of the find_method v-table call. An additional op that enables
the finding of a method using a different MRO would be required.

Attributes, if we wanted to allow a different MRO on them, would have an
analogous implementation.
--

Hope that this makes some kinda sense - feedback would be *very* welcome!

Take care,

Jonathan

Nicholas Clark

unread,
Mar 10, 2007, 12:10:07 PM3/10/07
to Jonathan Worthington, perl6-i...@perl.org
On Sat, Mar 10, 2007 at 04:51:28PM +0000, Jonathan Worthington wrote:

> Different languages may have a different MRO. Python since 2.3 and Perl
> 6 by default use C3. Perl 5 used something else. Therefore, we need

uses

> Hope that this makes some kinda sense - feedback would be *very* welcome!

Pedant point, I know, but any suggestion that Perl 5 is "special biologist
word for stable" seems to raise some hackles with the
over-sensitive-but-less-than-sensitive-about-it.

Brandon Black has been working on making (IIRC) pluggable MRO for Perl 5 -
you might want to talk to him. We've not been able to give him much helpful
feedback on the implementation of that, because all the Perl 5 MRO code
predates "change 1" - the import of 5.003 to perforce in 1997. I suspect it
goes back to 5.000. As part of "we", I've really not thought about the
implications of this sort of thing.

Does it actually work having different classes in the same hierarchy
declaring their own MRO? For example, if A-F declare themselves to be
leftmost depth first (or whatever the correct term is for Perl 5's order),
but G-I declare themselves to be C3, will it work?

A
/ \
B C
/ \ / \
D E F
\ / \ /
G H
\ /
I


Specifically because I thought that with C3, in

J
/ \
K L
\ /
M

the search order is M, K, L, J, whereas Perl 5 does M, K, J, L.

So if the top diamonds are ordered the Perl 5 way, they flatly contradict
the guarantee of C3.

It might be that I'm confused, misremembering or undercaffeinated.

Nicholas Clark

Larry Wall

unread,
Mar 10, 2007, 1:13:16 PM3/10/07
to perl6-i...@perl.org
On Sat, Mar 10, 2007 at 04:51:28PM +0000, Jonathan Worthington wrote:
: More interesting is that, for Perl 6,
: we also need to override the MRO on a by-method-call basis - you can
: change the dispatch order at the call site!

I wouldn't worry about that at all. I imagine such a construct
would simply turn into a direct sub call to the alternate dispatcher.

Larry

Jonathan Worthington

unread,
Mar 10, 2007, 1:09:40 PM3/10/07
to perl6-i...@perl.org
Nicholas Clark wrote:
> On Sat, Mar 10, 2007 at 04:51:28PM +0000, Jonathan Worthington wrote:
>
>
>> Different languages may have a different MRO. Python since 2.3 and Perl
>> 6 by default use C3. Perl 5 used something else. Therefore, we need
>>
> uses
>
>
>> Hope that this makes some kinda sense - feedback would be *very* welcome!
>>
>
> Pedant point, I know, but any suggestion that Perl 5 is "special biologist
> word for stable" seems to raise some hackles with the
> over-sensitive-but-less-than-sensitive-about-it.
>
Argh, dammit. That was likely a typo or I meant "chose to use at the
time it was designed", but count it as what you want. I know full well
Perl 5 isn't dead. At least, I hope it's not, because I use it all the
time in my day job and expect to be doing so for a long time yet. :-)
And no, it's not pedant at all - I'm well aware of the issue you mention
and really don't want to be seen in the "Perl 5 is dead" camp. Thanks
for giving me a chance to clear that up.

> Brandon Black has been working on making (IIRC) pluggable MRO for Perl 5 - you might want to talk to him. We've not been able to give him much helpful feedback on the implementation of that, because all the Perl 5 MRO code predates "change 1" - the import of 5.003 to perforce in 1997. I suspect it goes back to 5.000. As part of "we", I've really not thought about the implications of this sort of thing.
>

Thanks for the lead.

> Does it actually work having different classes in the same hierarchy
> declaring their own MRO? For example, if A-F declare themselves to be
> leftmost depth first (or whatever the correct term is for Perl 5's order), but G-I declare themselves to be C3, will it work?
>
> A
> / \
> B C
> / \ / \
> D E F
> \ / \ /
> G H
> \ /
> I
>
>
> Specifically because I thought that with C3, in
>
> J
> / \
> K L
> \ /
> M
>
> the search order is M, K, L, J, whereas Perl 5 does M, K, J, L.
>
> So if the top diamonds are ordered the Perl 5 way, they flatly contradict the guarantee of C3.
>
> It might be that I'm confused, misremembering or undercaffeinated.
>

It's a confusing problem, for sure. I've thought about it, but as of yet
have no good answers. I don't think forbidding having classes with
different MROs in a single hierarchy is the answer, because that loses a
lot of the inter-language stuff that we want.

One option is to say that a class cannot have a different MRO than its
parent class, so if it's a conflict we take the parent class's chosen
MRO. That makes classes you inherit from work. It may be confusing for
people subclassing them in another language, but on the other hand you
have explicitly stated that you are pulling in a class from another
language (since the language name is in the namespace), there's a clue
about what you should expect. Of course, once you get three languages
down the tree, you have no clue which one your MRO is coming from just
by glancing at the import line. Which means in general you don't know. Hmm.

I can't really think of any other options at the moment, or at least
anything that's even vaguely sane.

Thanks,

Jonathan

Larry Wall

unread,
Mar 10, 2007, 1:22:37 PM3/10/07
to perl6-i...@perl.org
On Sat, Mar 10, 2007 at 06:09:40PM +0000, Jonathan Worthington wrote:
: It's a confusing problem, for sure. I've thought about it, but as of yet
: have no good answers. I don't think forbidding having classes with
: different MROs in a single hierarchy is the answer, because that loses a
: lot of the inter-language stuff that we want.
:
: One option is to say that a class cannot have a different MRO than its
: parent class, so if it's a conflict we take the parent class's chosen
: MRO. That makes classes you inherit from work. It may be confusing for
: people subclassing them in another language, but on the other hand you
: have explicitly stated that you are pulling in a class from another
: language (since the language name is in the namespace), there's a clue
: about what you should expect. Of course, once you get three languages
: down the tree, you have no clue which one your MRO is coming from just
: by glancing at the import line. Which means in general you don't know. Hmm.
:
: I can't really think of any other options at the moment, or at least
: anything that's even vaguely sane.

I look at it this way. When you want to find the ancestors of a particular
object, you ask its metaobject for a list. That metaobject may either choose
to generate the entire list itself or delegate some of that generation either
to the ancestors in question or to some cooperative system such as C3. But
you can't tell the metaobject which of those approaches it should choose.
That's what's meta about it. It's supposed to tell you how, not you it how.

Larry

Jonathan Worthington

unread,
Mar 10, 2007, 2:34:17 PM3/10/07
to perl6-i...@perl.org
Aha, and that dispatcher can find the method thanks to all of the
metaclass stuff. Makes sense - looks like Parrot can punt on directly
providing for this construct then. :-)

Jonathan

Reply all
Reply to author
Forward
0 new messages