torus solutions!

最近よくコンティニュエーション・パッシングだとか、 継続ベースの○○とか、 そういう話題を耳にします。 でも継続っていうのが何なのか良く分からなかったので、 お正月休みに Shiro Kawaiさんの なんでも継続 を読んでみました。

---

今までずっと難しいだろうと思って読んでなかったんだけど、 これがまたとても分かりやすくて面白かったので、 途中にあげられていたサンプルコードを Perl でも書いてみました。

普通の再帰形式

Scheme では

(define (leaf-count tree)
  (if (pair? tree)
      (+ (leaf-count (car tree))
	  (leaf-count (cdr tree)))
      1))

Perl では

Perl にはペアがないので、 2 要素の配列でエミュレートすることにします。

それ以外はそのまんまです。

sub leaf_count {
    my ($tree) = @_;

    if (ref $tree) {
	 &leaf_count ($tree->[0])
	     + &leaf_count ($tree->[1]);
    } else {
	 1;
    }
}

継続渡し形式

Scheme では

(define (leaf-count/cps tree cont)
  (if (pair? tree)
      (leaf-count/cps (car tree)      
		       (lambda (n)
			 (leaf-count/cps (cdr tree)
					 (lambda (m) (cont (+ n m))))))
      (cont 1)))

Perl では

基本的には、 lambda を sub にすればいいだけだと思うけど、 sub の中に sub を書くときは、 ちょっと注意が必要みたい。（Perl のバグ？）

sub leaf_count_cps {
    my ($tree, $cont) = @_;

    if (ref $tree) {
	 &leaf_count_cps ($tree->[0],
			  sub {
			      my ($n) = @_;
			      my $dummy = $cont; # なぜか必要みたい。
			      &leaf_count_cps ($tree->[1],
					       sub {
						   my ($m) = @_;
						   $cont->($n + $m);
					       });
			  });
    } else {
	 $cont->(1);
    }
}

Scheme の values に対応する手続きを作って実行します。

my $tree = [["a", "b"], [["c", "d"], "e"]];

sub values {@_}
print &leaf_count_cps ($tree, \&values), "\n";

実行するとちゃんと 5 がでました。

ファーストクラスの継承？

call/cc を Perl で作ることはできるかなぁ。

Python 使いの田原さんは、 Zope で継続ベース風 Web アプリをつくちゃった そうなんですが、 Perl でも似たようなものは作れるかな。

「なんでも継続」の後半のまだかかれていない部分で、 C での実装にも触れられるような感じなので、 それを楽しみにしていよう。

Comments