Perl 5のgotoには、3種類ある。

1. goto LABEL

   こちらはCなどで見られるgotoと等価である。

   goto END;
   print "Hello\n";
   END:
     print "Goobye\n";
   

   Goodbye
   

2. goto EXPR

   こちらはちょっとひねったgotoだが、前の例と変らない。EXPRが返した値をLABELとみなすだけだ。

   for (0..2){
      goto ('foo', 'bar', 'baz')[$_];
      foo: print "foo ";
      bar: print "bar ";
      baz: print "baz ";
      print "\n";
   }
   

   foo bar baz 
   bar baz 
   baz 
   

3. goto &CODE

   これだけは他とあからさまに違う。これは一体なんなのか?

これを理解するには、実際のコードを追うに限るだろう。

まずは、普通のreturnの場合。

sub foo {
    print "foo: hello\n";
    bar();
    print "foo: goobye\n"
}

sub bar {
    print "bar: hello\n";
    baz();
    print "bar: goobye\n"
}

sub baz {
    print "baz: hello\n";
    print "baz: goobye\n"
}

foo();

実行すると、以下のとおりになる。

foo: hello
bar: hello
baz: hello
baz: goobye
bar: goobye
foo: goobye

まさに右の図aのとおりだ。この図はshiroさんの「なんでも継続」からお借りした。レイアウトの都合上、hotlinkではなくもともと一つの図を二つにさせてもらった。この場を借りて事後承諾をお詫びし、使いやすい図を作って下さったことに感謝する。

今度は、gotoを見てみよう。

sub foo {
    print "foo: hello\n";
    goto &bar;
    print "foo: goobye\n"
}

sub bar {
    print "bar: hello\n";
    goto &baz;
    print "bar: goobye\n"
}

sub baz {
    print "baz: hello\n";
    print "baz: goobye\n"
}

foo();

今度はこうなる。

foo: hello
bar: hello
baz: hello
baz: goobye

一端gotoしたら、元の関数には戻って来ない。そしてgoto先では、あたかもその関数が直接呼ばれたように見える。

このgotoが一番よく使われるのは、AUTOLOADとの組み合わせだ。すでに実例を404 Blog Not Found:Perl Monger の質問 - AUTOLOADって他でどうやるの?で書いたのでここでは詳しく触れないが、goto版と非goto版の一番の違いは、goto版ではAUTOLOADは一度しか呼ばれないということ。多数のaccessor/mutatorを動的に生成するには最高の方法である。

しかし、本当に面白いのはここからである。

例えば、フィボナッチ数を計算するプログラムを考える。再帰(recursive)でかけばこうなる。

sub fib_r{
    my $n = shift;
    return $n if $n <= 2;
    return fib_r($n-2) + fib_r($n-1);
}

が、これは鬼のように遅い。25を過ぎるあたりから、目に見えて遅くなるのがわかるはずだ。なぜならこれは再帰のたびに自分を一度ではなく二度づつ呼ぶ。自分自身を呼ぶ回数は2のベキで増えて行くのだ。

たいていこうした場合、メモ化(memoize)するか、再帰なしで書き直すかのどちらかだ。再帰なしで書き直すとこんな感じだろうか。

sub fib_i{
    my $n = shift;
    return $n if $n < 2;
    my ($f1, $f2) = (1, 1);
    ($f1, $f2) = ($f2, $f1 + $f2) while ($n-- > 1);
    return $f2;
}

この非再帰版をよく眺めてみると、$f1と$f2という二つの状態を持っていて、それを停止条件が来るまでループで回していることがわかる。この状態をレキシカル変数ではなく、引数として渡してやれば末尾再帰(tail-recursive)になる。

それが以下である。

sub _fib_g{
    my ($n, $f1, $f2) = @_;
    return $f2 if $n == 0;
    # _fib_g($n - 1, $f2, $f1 + $f2)
    @_ = ($n - 1, $f2, $f1 + $f2);
    goto  &_fib_g;
}
sub fib_g{ _fib_g(shift, 0, 1) };

そう。実はPerlでは、引数は上書き可能なのである。そして引数を上書きして自分自身にgotoすれば、returnなしの、「最適化された」末尾再帰が実現する。

しかも見てのとおり、末尾再帰を「最適化」するのは、それほど難しくないのである。

1. まず普通に関数を末尾再帰に書く。
2. return myself(args ...)を、以下のように書き換える。

@_ = (args ...);
goto &myself;

なんとこれだけである。ソースフィルターでも出来そうである。

以下、fib(25)でベンチマークしてみた結果である。さすがに普通の非再帰版にはかなわないが、単純な再帰版よりはずっと高速であるし、末尾再帰になっていてもgotoを使っていないものに比べても確かに速い。

         Rate     recr     tail     goto     iter     memo
recr   4.25/s       --    -100%    -100%    -100%    -100%
tail   9772/s  229909%       --     -30%     -79%     -92%
goto  14008/s  329626%      43%       --     -70%     -89%
iter  47284/s 1112897%     384%     238%       --     -63%
memo 128061/s 3014265%    1211%     814%     171%       --

ここまでくれば、CPSを実現するのもあと一歩だ。leaf_count_cps()は、以下のようになる。今度は「似非」ではない、本物の継続である。

sub leaf_count_cps {
    no warnings 'recursion';
    my ($tree, $cont) = @_;
    return $cont->(1) unless ref $tree;
    @_ = ( $tree->[0],
           sub {
               my $n = shift;
               my $c = $cont;
               @_ = ($tree->[1],
                     sub{
                         my $m = shift;
                         $c->($n + $m)
                     });
               goto &leaf_count_cps;
           });
    goto &leaf_count_cps;
}

もっとも、速度が遅いのは相変わらずである。動的にsubを生成するコストが高いためだ。以下はleaf nodeが2048個の場合をベンチマークしたものだ。1/12の速度というのは、それを考慮すればましなのかも知れない。

             Rate pseudo_cps        cps  recursive
pseudo_cps 17.8/s         --        -1%       -92%
cps        18.0/s         1%         --       -92%
recursive   231/s      1197%      1184%         --

Perl 5の変幻自在さを再確認。駱駝も踊る。

Dan the Continuation-Passing Perl Monger