2005年08月28日 21:42 [Edit]

継続は力なり

LLDN2005、みなさんお疲れさまでした。私は寝不足もあって今日は一日中死んでました。昼の部夜の部に関してすでにレポートがいくつか上がっています。


Perl6 and Parrot Essentials

Randall/Sulgaski/Tötsch

本blogでは、順不同にLLDN2005では扱いきれなかった「宿題」を片付けて行く事にします。まずは継続について。


会場Kahuaへの質疑問答の中で、継続に関する質問が失礼ながらとんちんかんで、言語屋にとっては常識である継続(continuation)も、まだまだ一般的に理解されているとは言えないことを実感した。すでにgaucheのShiroさんによる「なんでも継続」などのすばらしい解説があるにも関わらず、ここで蛇足的な説明と、そしてParrotとの関係なども説明してみる。

生活の中で家をメインすると、出勤するのはサブルーチンのようなものだ。自分(引数)を会社に出勤させ、給料(戻り値)を持って家に戻る。これが継続だと、通勤するのではなく、会社に家財を全部引っ越してからそこで仕事をするような感じだ。

「そんなバカな」と思うだろう。しかしこれだと「帰宅」という作業がなくなるというご利益がある。電脳の世界では実は継続というのはご利益満載で、末尾再帰が単なる呼び出し(goto)になったり、例外処理がずっとエレガントにできるようになったりというわけで、一旦理解してしまえばこれほど役にたつ概念はないほどだ。

継続はすでにLispでは私の年齢以上の歴史のある、古くて新しい概念だ。SchemeRubyのように、明示的に継続をサポートする電脳言語も多い。そうでない言語でも、関数を関数に渡すことのできる言語では同様のことを実現できる。ではPerlはどうかというと、実はあるのである。それもgotoという形で。

基本的な書き方は、LLDN夜の部で発表してくれたとおるさんの「なんでも継続、Perlで。」の通りなのだがこのままだと実際の処理では、もはや戻る必要のない呼び出し元まで呼び戻されてしまう。ちなみにここの例でとおるさんの例よりperlっぽくrefactorしてある。

sub leaf_count_cps {
   my ($tree, $cont) = @_;
   unless (ref $tree){
       $cont->(1);
   }else{
       leaf_count_cps($tree->[0],
                      sub {
                          my $n = shift;
                          my $cc = $cont;
                          leaf_count_cps($tree->[1],
                                         sub { $cont->($n + shift) }
                                         )
                          });
   }
   # 実際にはここに戻ってくる
}

厳密にやるには、gotoを使って以下のようにする。

sub leaf_count_cps_g {
    my ($tree, $cont) = @_;
    unless(ref $tree){
        $cont->(1);
    }else{
        my $cps = sub {
            my $cc = $cont;
            leaf_count_cps_g($tree->[0],
                             sub {
                                 my $n = shift;
                                 leaf_count_cps_g($tree->[1],
                                                  sub { $cont->($n + shift) });
                             });
        };
        goto &$cps;
    }
    # ここにはもはや戻らない
}

それで、明示的にやってご利益が感じられるかというと、残念ながらそうは行かない。明示的に継続渡しにした場合、その継続そのもので引数が一つ増え、全体の処理もずっと増えてしまう。なにしろ普通に書いた場合、こんなに簡単なのだ。

sub leaf_count {
   my ($tree) = @_;
   unless (ref $tree){
       1;
   }else{
       leaf_count($tree->[0]) + leaf_count($tree->[1]);
   }
}

ましてや以下のBenchmarkを見ると、「継続ってどこがいいねん?」という感じにもなるだろう。

             Rate  CPS-Goto       CPS Recursive
CPS-Goto   4699/s        --      -45%      -92%
CPS        8509/s       81%        --      -85%
Recursive 57415/s     1122%      575%        --

継続はご利益が多い反面、なかなかひち面倒でもあるのだ。こういう事は言語が裏でよきに計らってくれるに限る。そしてparrotでは、まさにそのとおりにしてくれるのだ。

Perl6 and Parrot Essentials pp.124
As a result, Parrot implements a full CPS system internally, and uses it for all subroutine and method calls.

拍手!「え、でもParrot Assembler(PASM)を直に扱う人は大変そう!」と思った方、ご安心を。

We also have the simpler call/return style of flow control available for alnguages that don't neeed the heavier-weight call system, as well as for compilers to use for internal processing and optimization.

なんともうれしいことに、

We do go to some lengths to hide the continuations. PIRcode, for examble, allows compiler writers to create subroutines and methods (and call to them) that conform to Parrot's CPS mechanism without ever touching continuations directly.

ということで、一般ピープルは継続の面倒なところに触れずにおいしいところだけ味わえるようになっている。Perl6とPugsの派手さの中で見えにくいが、実はParrotもすごいのである。

Dan the Just Another Continuation-Passing Perl Hacker

追伸: そうそう。言い忘れましたが、同書によると、ParrotでのCPSのサポートは、もともとはRubyのために開発がスタートしたそうです。

追記[2006.11.18]:

Tociyuki::Diary - Perl 5.8 で似非継続
再帰呼び出しと継続呼び出しが、goto になってしまっているのが、汚いですねぇ。まるで、BASIC みたいになってしまいました。

本entryは見落としたのかな?


この記事へのトラックバックURL

この記事へのトラックバック
Perlでもgotoを使えば、本当の継続(continuation)が可能であることを示す。 継続ってなんのことだかさっぱりわからない一は、以下にあらかじめ目をとおしておいていただきたい。 なんでも継続 なんでも継続、Perl で。 : torus solutions! 404 Blog Not Found:継...
perl - to goto or not to goto, that's the continuation【404 Blog Not Found】at 2007年04月18日 06:51
torus solutions! さんの「なんでも継続、Perl で。」のコード例は Scheme なら確かに継続になっているのですが、Perl では末尾関数呼び出しを goto にしてくれないので、クロージャをスタックに積み上げる再帰呼び出しのまんまです。 (11月18日追記)この問題を小飼弾さんが
[Perl]Perl 5.8 で似非継続【Tociyuki::Diary】at 2006年11月18日 11:56
Rubyの力はブロックにありと常々主張している。その文脈導入の力。そして、それ...
Rubyの力、すなわちブロックなり【ratio - rational - irrational】at 2006年04月11日 17:40
そうそう。このスライドを紹介するのを忘れていた。 現時点でのPerl6の最新にして最高の教科書が、ParrotとPugsのソースを除けばこれ。
Apocalypse Now!【404 Blog Not Found】at 2005年08月31日 11:55
LL Day - ちょっと時間をおいてから、改めて感想。ついでに公式サイトへのトラックバックからいくつか拾ったリンク集。
LLDN (7) - 補遺【ratio - rational - irrational】at 2005年08月30日 04:05
この記事へのコメント
なぜか海外からのcomment spamが多いので、本Entryのcomment欄のみとりあえず閉鎖します。
Dan the Owner Thereof

Posted by at 2006年03月11日 21:38