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:ほんとは再帰呼び出ししてるけど、僕がわかりやすいように書き下してます。