継続

継続、continuationと来ればやはりSchemeの話になるのだろうか。一般社会で schemeと言えば「すきーむ（n）計画。陰謀。」であるがソフトウェア業界で Schemeと言ったらLispの一種のことだ。Lispには変種が腐るほど存在するが、 Common Lispと並んで有名なのがSchemeである。Common Lispが標準化の課程でゴテ ゴテと装備して巨大化したのに対し、Schemeは遥かにコンパクトでクリアな仕 様を持つ。またSchemeとは言語の一般名であり、その実装にはGaucheとか scmとかguileとかMIT Schemeなどがある。

さてCall/CC、正式名称Call with Current Continuation、について 説明しよう。Call/CCはちょっと見はsetjmp/longjmpと同じように見えるのだが、 スタックが深くなる方向にもジャンプできるところが根本的に違う。例えば setjmp/longjmpでは 

main A B C D (setjmp) E F G

という状態からlongjmpすると 

main A B C D

に戻ることができた。だがCall/CCはこれをさらに凌駕する。 

main A B C D (call/cc) E F G

という状態から 

main A B x y z

となったとしても、Continuation#callを呼ぶことで 

main A B C D

に復帰できてしまうのだ。つまり既に終了したスタックフレームを黄泉の国か ら引きずり出してスタックにぶちこめるわけである。このときcall/ccが返す 「スタックなどのコンテキストを記憶したもの」をContinuation（継続）と 呼ぶのだ。

setjmp/longjmpだけでも相当に危険なワザなのに、ここまで来ると考えるだけ でも恐ろしい。これは単なる気分の問題ではなく、かなり注意して使わないと あっさり無限ループに突入したりする。はっきり言って普通は使わないし、 お勧めもしない。

そもそもCall/CCがrubyに実装されている理由はただ一つで、「実装できてし まったから」である。最近のRuby関連メーリングリストの流れを見ていると 「Call/CCステ」の方向で あるのは間違いない。まあ、普通の人間が「おっ、ここはCall/CCを使えば カッコ良く実装できるね！」などと思いついたりすることはまずありえないので、 ある意味安心である。

Call/CCの実装

というわけでどうして実装できてしまったのか見ることにしよう。

Call/CCの実装に必要なのは、プログラムのコンテキストである。 これはまさにRubyスレッドの実装でやっていることだ。 それゆえCall/CCの実装は非常に単純で、 関数を二つ見ておけばほとんどカバーできる。 Continuationを生成するrb_callcc()と、 保存した状態に復帰するrb_cont_call()だ。 

static VALUE
rb_callcc(self)
    VALUE self;
{
    volatile VALUE cont;
    rb_thread_t th;
    struct tag *tag;
    struct RVarmap *vars;

    THREAD_ALLOC(th);
    cont = Data_Wrap_Struct(rb_cCont, thread_mark, thread_free, th);

    scope_dup(ruby_scope);
    for (tag=prot_tag; tag; tag=tag->prev) {
	scope_dup(tag->scope);
    }
    if (ruby_block) {
	struct BLOCK *block = ruby_block;

	while (block) {
	    block->tag->flags |= BLOCK_DYNAMIC;
	    block = block->prev;
	}
    }
    th->thread = curr_thread->thread;

    for (vars = th->dyna_vars; vars; vars = vars->next) {
	if (FL_TEST(vars, DVAR_DONT_RECYCLE)) break;
	FL_SET(vars, DVAR_DONT_RECYCLE);
    }

    if (THREAD_SAVE_CONTEXT(th)) {
	return th->result;
    }
    else {
	return rb_yield(cont);
    }
}

使っているデータ構造はまるっきりスレッドと同じで、クラスだけが違う。

そしてトップレベルから現在までの全てのSCOPEとBLOCKをスタックからヒープ に移し、Varmapをリサイクル禁止にする。Call/CCではときに終了したスタック フレームも復活させなければならないからである。

最後に、THREAD_SAVE_CONTEXT()で保存またはreturnする。返り値がゼロの ときが初回、非ゼロのときが復帰であった。初回はそのままContinuationを yieldし、どこかからジャンプで戻ってきたときはジャンプの返り値を返す。

rb_cont_call

rb_cont_call()はContinuationオブジェクトとして保存されたコンテキストに 復帰するための関数である。この関数も絶対にreturnしない。 

static VALUE
rb_cont_call(argc, argv, cont)
    int argc;
    VALUE *argv;
    VALUE cont;
{
    rb_thread_t th = rb_thread_check(cont);

    if (th->thread != curr_thread->thread) {
	rb_raise(rb_eRuntimeError, "continuation called across threads");
    }
    switch (argc) {
      case 0:
	th->result = Qnil;
	break;
      case 1:
	th->result = *argv;
	break;
      default:
	th->result = rb_ary_new4(argc, argv);
	break;
    }

    rb_thread_restore_context(th, RESTORE_NORMAL);
    return Qnil;
}

チェックと引数の変換、そしてrb_thread_restore_context()でスタックを 書き戻して終了だ。コードも短いが解説も短い。 Continuationの実装は本当に意外なほど簡単だ。

もっとも実装時にはいろいろと紆余曲折があった。終了したスタック フレームが再利用されるなどそれまでは考えられていなかったわけだし、 conservative GCとスタック操作がからむと非常にややこしいことになる。 このへんのいきさつは [ruby-dev:4084] あたりを読むとわかる。

Copyright (c) 2002 Minero Aoki <aamine@loveruby.net>