IT戦記

プログラミング、起業などについて書いているプログラマーのブログです😚

Class::C3, Algorithm::C3 を勉強したよ!

DBIx::Class を少し使ったことがあったので

Class::C3 をなんとなくで理解していたんです。(ふーん幅優先版の NEXT モジュールでしょ?みたいな感じで。)
でも、これは絶対にちゃんと細かい挙動まで勉強しといたほうがいいと思いました。
多重継承とか mixin とかに強くなりたいなと

C3

C3 というのは Python 2.3 のドキュメントに書いてある MRO(Method Resolution Order 多重継承したときにどんな感じでメソッドを探索するかという順番) を決めるアルゴリズムで。Algorithm::C3 っていうのがそのアルゴリズムPerl 実装なんです。
それに! Parrot でも使えるみたいだし!

ちなみに MRO ってこんな感じね

A には add というメソッドがある B にも add というメソッドがある C は A と B を多重継承している。
さて、C の add を呼ぶとどっちの add が優先されるでしょう?
みたいな、優先順位ね。

とりあえず、Algorithm::C3 のソースを読む

http://search.cpan.org/src/BLBLACK/Algorithm-C3-0.05/lib/Algorithm/C3.pm
。。。。ぜんぜん分からなくて、泣きたくなりました。

作戦変更

ドキュメントを読んでみる。
http://mirrorspace.org/python/2.3/mro.html
ドキュメントは読まない主義だけど、ソースを読んで理解できなかったので (;_; シクシク

英語でさっぱりわかr . . . でも

式みたいなのがいっぱいあったので、英語と組み合わせていろいろしてるうちに理解できてきた!

use strict;
use warnings;

use Algorithm::C3;

package A;
package B; our @ISA = qw/A/;
package C; our @ISA = qw/A/;
package D; our @ISA = qw/B C/;

print Algorithm::C3::merge('D', sub {
    my $class = shift;
    no strict 'refs';
    return @{$class."::ISA"};
});

このようなひし型の継承ツリーがあったとすると MRO は以下のように解ける

L[A] = A
L[B] = B L[A]
     = B A
L[C] = C L[A]
     = C A
L[D] = D merge(L[B], L[C], BC)
     = D merge(B A, C A, B C)
     = D B merge(A, C A, C)
     = D B C merge(A, A)
     = D B C A

答えは

DBCA

である。

この式みたいのはなんなの!?

この式は MRO 導出するための特殊な式みたいです。
http://mirrorspace.org/python/2.3/mro.html
ここに書いてあります。

式を口(言葉?)で説明すると

L[A] = A

A は何も継承してないので MRO は A だけ。

L[B] = B L[A] = B A

B は単一継承なので B の MRO は B の後に A の MRO を追加したものになる。

L[C] = C L[A] = C A

C も単一継承なので C の MRO は C の後に A の MRO を追加したものになる。

L[D] = D merge(L[B], L[C], BC) = D merge(B A, C A, B C)

D は B と C の多重継承なので、B の MRO と C の MRO と継承した順(qw/B C/の順番)の MRO を包括的(merge)に考えなければならない。

D merge(B A, C A, B C) = D B merge(A, C A, C)

D の次を考えてみる。
もし、A にすると B A の MRO に矛盾する。
もし、C にすると B C の MRO に矛盾する。
つまり、次にくるのは B である。(B は merge されたすべての MRO の 2 番目以降には存在しない)

D B merge(A, C A, C) = D B C merge(A, A)

D の次は B であるので、B を抜きにして考えると、C が merge されたすべての MRO の 2 番目以降に存在しない。
つまり、次は C である。

D B C merge(A, A) = D B C A

A と A は同じなので merge しても A となる。
これで D の MRO が求まった。

なるほど!

C3 は、すべての継承した順番(ISA配列の要素の順番)とすべての継承の深さ(継承した順番)に矛盾しないアルゴリズムということが言えるのか!!

じゃあ

逆に、こんな感じで C は A->B の順 D は B->A の順で継承してみる。
これだと、B が先にも A が先にもできないはず。つまり、どっちかの MRO は矛盾するはず。

use strict;
use warnings;

use Algorithm::C3;

package A;
package B;
package C; our @ISA = qw/A B/;
package D; our @ISA = qw/B A/;
package E; our @ISA = qw/C D/;

print Algorithm::C3::merge('E', sub {
    my $class = shift;
    no strict 'refs';
    return @{$class."::ISA"};
});

結果

nconsistent hierarchy found while merging 'E':
        current merge results [
                E,
                C,
                D
        ]
        merging failed on 'B'

おおおおおおおおお。ちゃんと失敗したぞ。すごい

あぁ。。ってことは

巨大な継承ツリーに以下のような矛盾が一個あるだけでエラーになっちゃうのか。

use base qw/Class::Accessor::Fast Class::Data::Accessor/;
use base qw/Class::Data::Accessor Class::Accessor::Fast/;

これは、厳しい。。。。
多重継承の順番とかプラグインの順番とかはちゃんと考えるようにしようっと。

まとめ

なんかがーっと書きなぐってみたけど、僕、 C3 なんとか理解できたよ!休日の勉強ってすばらしい!