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

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

shift/reset と control/prompt の違い

shift/reset 以外にも部分継続を扱うオペレータとして control/prompt というのがあります。この違いをすぐに忘れるのでメモ。
以下のコードは Olivier Danvy's puzzle と呼ばれているらしいです *1 。ちなみに Olivier Danvy は shift/reset 提唱者。

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

x = prompt do
  control {|k| [1] + k.call }
  control {|k| [2] + k.call }
  control {|k| [3] + k.call }
  []
end
p x #=> [3, 2, 1]

つまり reset のブロックが終わったとき、後に部分継続を呼び出した方から再開するのが shift/reset で、先に部分継続を呼び出した方から再開するのが control/prompt 。なんとなく、shift/reset がスタックで control/prompt がキューみたいな印象。というか control/prompt はバグってるぽいですね。

以下、control/prompt の実装 (元ネタ: http://okmij.org/ftp/Scheme/delim-control-n.scm) 。なんかややこしいですね。

require "continuation"

$ctns = []

def prompt
  callcc do |c|
    $ctns << [c, true]
    v = yield
    $ctns.pop.first.(v)
  end
end

def control
  callcc do |c1|
    cs = []
    cs.unshift $ctns.pop until $ctns.last.last
    k = proc do |v|
      callcc do |c2|
        $ctns += [[c2, false]] + cs
        # 上の false を true にすると shift/reset になる
        c1.(v)
      end
    end
    v = yield(k)
    $ctns.pop.first.(v)
  end
end

*1:ほんとは再帰呼び出ししてるけど、僕がわかりやすいように書き下してます。