僕でもわかる継続と部分継続

callcc と shift/reset についてわかるとこだけ書いてみます。

継続

callcc という操作は、現在から実行終了まで、継続をまるごと取り出します。例題。

p [1] + callcc {|k| [2] + k.call([3]) } #=> [1, 3]

callcc では callcc がリターンしてから実行終了するまでの継続 k が取り出せます。k.call([3]) で継続が呼ばれると、いきなり「callcc が [3] を返した瞬間」に実行が飛びます。つまりこんな感じ。

p [1] + [3]

あとは自明ですね。"[2] +" のあたりは無視されます。

部分継続

shift という操作は、現在から reset まで、継続の一部だけを取り出します。この継続の一部を部分継続といいます。例題。

p [1] + reset { [2] + shift {|k| [3] + k.call([4]) } } #=> [1, 3, 2, 4]

shift では shift がリターンしてから reset に到達するまでの部分継続 k が取り出せます。k.call([4]) で部分継続が呼ばれると、いきなり「shift が [4] を返した瞬間」に実行が飛びます。callcc と同じですね。

p [1] + reset { [2] + [4] }

そして reset のブロックは [2, 4] を返して終わります。すると今度はいきなり「k.call が [2, 4] を返した瞬間」に実行が飛びます。再開って感じ。

p [1] + reset { [2] + shift {|k| [3] + [2, 4] } }

shift のブロックは [3, 2, 4] を返して終わります。今度はまたいきなり「reset が [3, 2, 4] を返した瞬間」に実行が飛びます。飛びまくりですね。

p [1] + [3, 2, 4]

あとはそのまま。

ややこしい例

reset の中で複数回 shift するとややこしいですが、基本は同じです。

x = [1] + reset do
  shift {|k| [2] + k.call([3]) } +
  shift {|k| [4] + k.call([5]) } + [6]
end
p x #=> [1, 2, 4, 3, 5, 6]

k.call([3]) が呼ばれる。

x = [1] + reset do
  [3] +
  shift {|k| [4] + k.call([5]) } + [6]
end
p x

k.call([5]) が呼ばれる。

x = [1] + reset do
  [3] +
  [5] + [6]
end
p x

[3, 5, 6] が reset される。後に shift した方から順に再開していく感じ。ここでは k.call([5]) へ。

x = [1] + reset do
  shift {|k| [2] + k.call([3]) } +
  shift {|k| [4] + [3, 5, 6] } + [6]
end
p x

後半の shift のブロックが [4, 3, 5, 6] を返して終わるので reset に飛ぶけど、まだ shift が残っているのでそっちに飛ぶ。

x = [1] + reset do
  shift {|k| [2] + [4, 3, 5, 6] } +
  shift {|k| [4] + k.call([5]) } + [6]
end
p x

前半の shift のブロックが [2, 4, 3, 5, 6] を返して終わるので reset に飛ぶ。もう shift は残ってないのでそのまま reset が終わる。

x = [1] + [2, 4, 3, 5, 6]
p x

考察

なんだか飛びまくりでややこしいですが、要は部分継続の呼び出し k.call は「試しに shift をリターンさせて、reset に到達するまで実行して、その返り値を持ってくる」だけです。
また、上の最初の例では実は部分継続 k は proc {|arg| [2] + arg } と同じです。つまり、reset のブロックは 1 引数のクロージャであり、shift の呼び出しがその引数に置き換わっている、と見ることができます。

以上、Continuation Fest に行けなかったので、なんかぐだぐだ書いてみました。なんか間違ってたら教えてください。

おまけ

Ruby での shift/reset の実装。1.9 用。スレッドとかは考えない。

require "continuation"

def shift
  callcc {|c1| $ctn.(yield(proc {|v| callcc {|c2| $ctn = c2; c1.(v) } })) }
end

def reset
  callcc {|c| $ctn = c; v = yield; $ctn.(v) }
end