camel

Perl�Ǥ�goto��Ȥ��С������η�³(continuation)����ǽ�Ǥ��뤳�Ȥ򼨤���

��³�äƤʤ�Τ��Ȥ������äѤ�狼��ʤ���ϡ��ʲ��ˤ��餫�����ܤ�Ȥ����Ƥ����Ƥ�������������

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

    ���������¾�Ȥ����餵�ޤ˰㤦������ϰ��Τʤ�ʤΤ�?

��������򤹤�ˤϡ��ºݤΥ����ɤ��ɤ��˸¤��������

diagram-return

�ޤ��ϡ����̤�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�ǤϤʤ���Ȥ�Ȱ�Ĥοޤ���Ĥˤ����Ƥ��ä������ξ��ڤ�ƻ��徵�����ͤӤ����Ȥ��䤹���ޤ��äƲ����ä����Ȥ˴��դ��롣


diagram-return

���٤ϡ�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�Ȥ�����Ĥξ��֤���äƤ��ơ��������߾�郎���ޤǥ롼�פDz󤷤Ƥ��뤳�Ȥ��狼�롣���ξ��֤�쥭�������ѿ��ǤϤʤ��������Ȥ����Ϥ��Ƥ��������Ƶ�(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 ...)�򡢰ʲ��Τ褦�˽񤭴����롣
  3. @_ = (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