callcc と coroutine と semi-coroutine

Ruby で callcc を使って coroutine や semi-coroutine を書いてみました。あまり考えずに試行錯誤で書いたので間違ってるかもしれませんが、とりあえず晒してみます。

coroutine は Modula-2 で採用されているもの、semi-coroutine は Lua で採用されているもの *1 を実装したつもりです。

callcc で coroutine

まずサンプル。以下のコードは 1 、3 、2 を出力して終了します。

c1, c2 =
    Coroutine.new { p 1; c2.start; p 2 },
    Coroutine.new { p 3; c1.start; p 4 }

c1.start

$ ruby -rcoroutine test.rb
1
3
2

かいつまんで解説。

• coroutine.start で coroutine を起動します。
• start したときに実行していた coroutine は止まります。他の coroutine から止まった coroutine が start されたら、最後に止まった場所から再開します。サンプルでは、c2.start で c1 が止まり、その後 c2 内で c1.start されたとき、c2.start の直後から実行再開しています。
• いずれかの coroutine が終了するとプログラムごと終了します。サンプルでは、p 2 の直後で c1 が終了するのでそこでプログラム終了です。

以下 coroutine のソースです。callcc の練習問題ですね。簡単のため、スレッドや例外などは無視です。

class Coroutine
    @@cur = Coroutine.new
    attr_accessor :thunk

    def initialize
        # 残りの計算は「ブロックを実行してプログラムを終了する」
        @thunk = proc { yield; exit }
    end

    def start
        callcc do |c|
            @@cur.thunk = c # 残りの計算を更新する
            @@cur = self    # 現在の coroutine を更新する
            @thunk.call     # 現在の coroutine を開始 (または再開) する
        end
    end
end

coroutine で semi-coroutine

まずサンプル。以下のコードは 1 、3 、2 、4 を順に出力して終了します。

c1, c2 =
    SemiCoroutine.new { p 1; SemiCoroutine.yield; p 2 },
    SemiCoroutine.new { p 3; SemiCoroutine.yield; p 4 }

c1.resume  #=> 1
c2.resume  #=> 3
c1.resume  #=> 2
c2.resume  #=> 4

$ ruby -rsemicoroutine test.rb
1
3
2
4

こちらもかいつまんで解説。

• semi-coroutine は resume で起動します。semi-coroutine ã‚’ resume すると、resume した semi-coroutine と resume された semi-coroutine が親子になります。
• 自分の親や先祖の semi-coroutine は resume できません (親子関係はサイクルにならない) 。例えば、c1 の中で c2 ã‚’ resume し、その c2 の中で c1 ã‚’ resume することはできません。
• ただし直接の親だけは SemiCoroutine.yield という別の命令で起動できます。
• semi-coroutine が終了すると、yield したのと同じ効果になります。終了した coroutine はもう resume できません。

要約すると、semi-coroutine は coroutine にいろんな制限をかけたものです。多分。

ソースはこんな感じ。

require "coroutine"

class SemiCoroutine < Coroutine
    @@cur = SemiCoroutine.new
    @@stack = []
    private :start

    def initialize
        # 残りの計算は「ブロックを実行して yield する」
        @thunk = proc {|*args| yield(*args); @dead = true; SemiCoroutine.yield }
    end

    def resume(*args)
        raise "cannot resume semi-coroutine recursively" if @@stack.include?(self)
        raise "cannot resume dead semi-coroutine" if @dead

        @@stack << @@cur  # 実行中の semi-coroutine (= 次の親) を push
        start(*args)      # 子を呼び出す
    end

    def yield(*args)
        raise "cannot yield non-parent semi-coroutine" unless @@stack.last == self

        @@stack.pop       # 親をスタックから pop
        start(*args)      # 親を呼び出す
    end

    def SemiCoroutine.yield(*args)
        @@stack.last.yield(*args)
    end
end

上記の Coroutine を使って実装しました。resume も yield も結局 start です。違うのは、親子関係をあらわすスタックを push するか pop するか。あと、yield はスタックのトップ (直接の親) に対してしかできません。semi-coroutine が coroutine に制限をかけたものだということが見えるような見えないような。

semi-coroutine で coroutine

逆に semi-coroutine で coroutine をエンコードすることもできます (と Coroutine in Lua で主張されてます) 。多分こんな感じ。start は、master を yield して、master から次に実行するものを resume するため、親子関係のスタックが伸びないのがポイントです。

require "semicoroutine"

class Coroutine2 < SemiCoroutine
    @@master = SemiCoroutine.new do |c, *args|
        loop { c, *args = c.resume(*args) || exit }
    end
    @@first = true

    def start2(*args)
        if @@first
            @@first = false
            @@master.resume(self, *args)
        else
            @@master.yield(self, *args)
        end
    end
end

c1, c2 =
    Coroutine2.new { p 1; c2.start2; p 2 },
    Coroutine2.new { p 3; c1.start2; p 4 }

c1.start2

$ ruby -rcoroutine2 test.rb
1
3
2

まとめ

言いたいことは 3 つ。

• coroutine が使えないのは多分間違いない。
• semi-coroutine は結構ややこしいかも。使うだけならそうでもない？
• こういう実験を気軽にできる Ruby が好き。外部ライブラリ扱いでもいいから callcc 残るといいなあ。

*1:Lua で coroutine と呼ばれているものは実は semi-coroutine です。