[ruby-list:34943] Thread by callcc

原です。

callcc で Thread みたいなものを作る話です。

事の起こりは立石さんが [rubyist:1340] で、もうちょっと Continuation
の応用例で良いのをあげましょう、という話だったんですが、新井さんが、
Continuation なんかいらないんじゃないかと、暴言:-)を吐き、しまいには
まつもとさんも、Rite じゃやめちゃうかも、などと言う始末。一方、Tosh 
さんが、[rubyist:1352] で、choose という Non-deterministic Programming
を実現する非常に興味深い例をあげて、でもちょっとまずいところもあるん
だ、という話でした。

いい加減な要約だなあ。

それはそれとして、と私が下のような遅延評価クラスは、マニュアルに載
せる例としてはいいのではないか、と言ったところ、

-^ lazy-eval.rb
class LazyEvaluation
   def initialize
     if callcc{|@upper| false}
       yield(self)
       self.break
     end
   end

   def call
     if callcc{|@lower| true}
       self.redo
     end
   end

   def break
     @lower.call(false)
   end

   def redo
     @upper.call(true)
   end
end

if $0 == __FILE__
   bye = LazyEvaluation.new{
     puts "Bye"
   }
   puts "Hello"
   bye.call
end
-$ lazy-eval.rb

Tosh さんが、これを元に　[rubyist:1370] で、co_fork という形
にしたのでした。次のが私がまたそれを少し拡張したものです。

-^ co-thread.rb
class CoThread
   def initialize
     @threads = []
   end

   def enter
     callcc{|cc| @threads.push(cc); false }
   end

   def exit(x = nil)
     @threads.shift.call(true, x)
   end
   
   def fork
     sw, x = enter
     if sw
       r = yield(x)
       self.exit(r)
     end
     self
   end
   
   def pass(x = nil)
     sw, r = enter
     unless sw
       self.exit(x)
     end
     r
   end
end
-$ co-thread.rb

これによって、Thread とは違い、明示的に次のスレッドに処理を
渡すようなプログラムが書けます。次は 1 から 7 まで、0.5 刻
みで出力する例です。


   require "co-thread"
   ct = CoThread.new
   ct.fork do |x|
     puts x
     puts 2
     puts ct.pass(2.5)
     puts 5
     5.5
   end

   ct.fork do |x|
     puts x
     puts 3
     puts ct.pass(3.5)
     puts 6
     6.5
   end

   puts 1
   puts ct.pass(1.5)
   puts 4
   puts ct.pass(4.5)
   puts 7


前置きが長くなりましたが、この CoThread というのが、かなり良く出来て
いるかもしれない、と思うので説明します。

今までも、callcc を使う話は、カーソルとか [ruby-list:13696]、Queue 
みたいなのとか [ruby-list:13695]、あるいは、平行 each では、MUSHA 
さんの仕事が

   http://www.ruby-lang.org/~knu/cgi-bin/cvsweb.cgi/rough/lib/generator.rb

にあります。

さて、この CoThread を使うと、これらが統一的にまとめられます。
以下にあげるのは、

(1) Proc 互換クラス
(2) 平行 each
(3) 内部イテレータの外部イテレータへの変換
(4) Queue の CoThread 版

で、どれもシンプルで短いものです。


(1) Proc 互換クラス

-^ yaproc.rb
require "co-thread"

class YaProc < CoThread
   def self.new(&b)
     super.fork(&b)
   end

   alias call pass
end

if $0 == __FILE__
   by = YaProc.new{|x| "by" + x }
   puts "Hello"
   puts by.call("e")
end
-$ yaproc.rb


(2) 平行 each

-^ sync-each.rb
require "co-thread"
class SyncEach
   include Enumerable

   def initialize(*es)
     @ct = CoThread.new
     @size = es.first.size
     es.each do |e, i|
       @ct.fork do |a|
	e.each do |x|
	  a.push(x)
	  a = @ct.pass(a)
	end
       end
     end
   end

   def each
     @size.times do
       yield @ct.pass([])
     end
   end
end

if $0 == __FILE__
   foo = SyncEach.new(0..3, 10..13, 20..23)
   foo.each do |a|
     p a
   end
end
-$ sync-each.rb


(3) 内部イテレータの外部イテレータへの変換

-^ generator.rb
require "co-thread"

class Generator
   def initialize(enum, iter = :each, eoi = :eoi)
     @ct = CoThread.new
     @ct.fork do
       enum.send(iter) do |x|
	@ct.pass(x)
       end
       @ct.pass(eoi)
     end
   end

   def next
     @ct.pass
   end
end

if $0 == __FILE__
   g = Generator.new(0..3)

   while :eoi != (x = g.next)
     p x
   end

   puts

   module Fibonacci
     def self.each
       a, b = -1, 1
       loop do
	a, b = b, a + b
	yield b
       end
     end
   end
   
   g = Generator.new(Fibonacci)
   while (x = g.next) < 200
     p x
   end
end
-$ generator.rb


(4) Queue の CoThread 版

-^ co-queue.rb
require "co-thread"

class CoQueue
   def initialize(ct)
     @thread = ct
     @queue = []
   end

   def enq(x)
     @queue.push(x)
     @thread.pass
   end

   def deq
     while @queue.empty?
       @thread.pass
     end
     @queue.shift
   end
end

if $0 == __FILE__
   ct = CoThread.new
   qu = CoQueue.new(ct)

   ct.fork do
     (10..14).each do |x|
       qu.enq(x)
     end
   end

   ct.fork do
     (20..26).each do |x|
       qu.enq(x)
     end
     qu.enq :eoi
   end
   
   while :eoi != (x = qu.deq)
     p x
   end
end
-$ co-queue.rb


それぞれ、Thread を使うとかなり気を使わなければならないところが、
ずいぶん素直に書けていると思います。

CoThread という名前は Cooperating Thread のつもりだけど、もっとい
い名前はないですかね。co-sine とか、co-product などの co- の意味
があると取られてもいけないし。fork, pass もどうかな。


こんな風にライブラリを充実させていけば、callcc も生き延びられる？