Ruby に callcc を公式にサポートさせよう

Ruby の callcc というと、

現在の Ruby の Continuation は欠陥品で、まともに利用できないシロモノです。具体的には、dynamic-wind 相当の機能がありません。
(略)
ちなみに、dynamic-wind 相当の機能を入れるのは、拡張ライブラリを全部 callcc safe にする作業に相当しますので、現実的じゃないんじゃないかなぁ、と思っています。
ruby-dev:30988

という話があって、「そっかー欠陥品なのかー」「直すのも難しいのかー」と悲しんでいました。
が、dynamic-wind を実装するだけなら広範囲の修正は不要なことに気がつきました。つまり直すのは簡単。というエントリ。

その前に: dynamic-wind とは

dynamic-wind とは、継続呼び出しで指定した範囲に突入したり脱出したりするときに起動するハンドラを設定する関数です。
3 つの proc を受け取って、基本的にはそれらを順に呼び出します。

dynamicwind(
  proc { p :before },
  proc { p :thunk },
  proc { p :after }
)
#=> :before, :thunk, :after

真ん中の proc を継続呼び出しで脱出すると、普通は callcc のところへ一気に飛びますが、dynamicwind を使っていると最後の proc が実行されます。

callcc do |c|
  dynamicwind(
    proc { p :before },
    proc { c.call; p :thunk },
    proc { p :after }
  )
end
#=> :before, :after

つまり継続による脱出の場合でも、ファイルの close のような後始末ができるようになります。文法は全然違いますが、ensure 節みたいなものです。
逆に、真ん中の proc へ継続呼び出しで突入するとき、最初の proc が実行されます。

dynamicwind(
  proc { p :before },
  proc { callcc {|c| $c = c }; p :thunk },
  proc { p :after }
)
#=> :before, :thunk, :after

$c.call #=> :before, :thunk, :after, ...

これによって、再突入する際に前処理 (再入禁止のチェックなど) ができます。
基本的にはこれだけです。細かいことは R6RS や、guile や gauche のマニュアルなどを見てください。

Ruby での実装

これをどうやって実装するかというと、callcc の定義をちょっと書き換えて、こうします。

require "continuation"

Stack = Struct.new(:fst, :snd, :next)
$top = Stack.new(nil, nil, nil)

alias callcc_orig callcc

def callcc
  mark = $top
  callcc_orig do |ctn|
    yield proc {|ret| switch(mark); ctn.call(ret) }
  end
end

def dynamicwind(before, thunk, after)
  mark = $top
  switch(Stack[[before, nil], [nil, after], mark])
  thunk.call ensure switch(mark)
end

def switch(mark)
  return if $top.equal?(mark)
  switch(mark.next)
  fst, snd = mark.fst, mark.snd
  fst.first.call if fst.first
  $top.fst = snd
  $top.snd = fst
  $top.next = mark
  $top = mark
  $top.fst = nil
  $top.snd = nil
  $top.next = nil
  fst.last.call if fst.last
end

言葉では説明しにくすぎるのですが一応説明しますと、ポイントは switch の fst と snd です。dynamic-wind の範囲に入るときと出るときに fst と snd を入れ替えます。これによって、dynamic-wind の範囲の外にいるときは fst =「before の proc」、snd =「after の proc」であり、中にいるときは fst =「after の proc」、snd =「before の proc」であるようになってます。よって call されるのは常に fst の方。
あと switch によって $top と mark の参照が巧妙に入れ替わり、switch 後は $top が mark の後ろを指している感じです。気合いでわかってください。

C での実装

まだやってません。が、上記の実装のように、

今の callcc をちょっと変える
dynamicwind と switch を実装する
struct rb_thread_t に $top 相当のフィールドを持たせる

だけでできるはずです。拡張ライブラリやその他広範囲にわたる変更は必要ありません。ないはずです。後でちゃんとやる。

影響範囲

callcc が「欠陥品」でなくなる
callcc が若干遅くなる (が、もともととても遅いので誤差範囲)
callcc を使わない限り影響はない (恒常的な速度劣化などはしない)

dynamic-wind で callcc が安全になるか

dynamic-wind は「継続呼び出しによる脱出や再入の際に前処理や後始末をする機構」を提供するだけです。なので、外部ライブラリが dynamic-wind を使って脱出や再入の対策をしていないと、やはり安全ではないです。そういう意味で、結局「ライブラリを全部 callcc safe にする作業」は必要になります。がっかり。
しかし、Ruby にはそういう「これをすると他のライブラリが変なことになること」は山ほどあります。例えば、組み込みクラスのメソッドを書き換えるとか (例: mathn) 。へたに *_missing を定義すると怪しいことになるとか。他には set_trace_func を使うと「set_trace_func を使うライブラリ」は使えなくなるし、拡張ライブラリで怪しいところで例外起こせばメモリリークとか close し忘れとかする可能性はあると思います。これらの黒魔術は公式サポートで、callcc はダメという理由は、ないんじゃないかなあ。

おまけ

上記の実装をちょっとだけ直したものを github に置きました。

gem install mame-dynamicwind --source=http://gems.github.com/

でインストールできます。1.8 でも 1.9 でも動くはず。暇な人はこの実装をいじめてみてください。