[ruby-list:34952] Re: Thread by callcc

In article <[e-mail]>,
  Shin-ichiro HARA <[e-mail]> writes:

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

個人的には callcc のような怪しい機能は大好きなのですが、知合いの
callcc 有害論ももっともだと思うこともあり、態度を決めかねていたりしま
す。

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

これって単にロックを書かなくていいというだけでは?

だとしたら、むしろスレッドの亜種としてコルーチンのサポートを入れるとい
う手もあるのでは?

と、思ったので、試してみました。

コルーチンを coroutine.rb というので(内部でスレッドを使って)実装し、

> (2) 平行 each
> (3) 内部イテレータの外部イテレータへの変換

と同じ API をコルーチンで作りなおしてみました。

coroutine.rb は次のようなものです。

--- coroutine.rb ---
require 'thread'

class Thread
  def mutex
    @mutex = Mutex.new unless defined? @mutex
    @mutex
  end

  def resume(val=nil)
    self.mutex.lock
    @val = val
    self.run
    Thread.current.mutex.unlock
    Thread.stop

    self.queue.enq val
    Thread.current.queue.deq
  end
end

class Coroutine < Thread
  def initialize(&block)
    caller = Thread.current
    super() {
      Thread.stop

      caller.resume block.call(self.queue.deq)
    }
  end
end

if $0 == __FILE__
  main = Thread.current
  c = Coroutine.new {|a|
    p a
    p 2
    p main.resume(2.5)
    p 4
    p main.resume(4.5)
    p 6
    p main.resume(6.5)
  }
  p 1
  p c.resume(1.5)
  p 3
  p c.resume(3.5)
  p 5
  p c.resume(5.5)
end
------

で、これを使うと sync-each.rb と generator.rb は次のように書けます。

--- sync-each.rb ---
require 'coroutine'

class SyncEach
  include Enumerable

  def initialize(*es)
    @size = es.first.size
    @cs = es.map {|e|
      Coroutine.new {|t|
        e.each {|x|
	  t = t.resume x
	}
      }
    }
  end

  def each
    @size.times {
      yield @cs.map {|c| c.resume(Thread.current)}
    }
  end
end

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

--- generator.rb ---
require 'coroutine'

class Generator
  def initialize(enum, iter = :each, eoi = :eoi)
    @c = Coroutine.new {|t|
      enum.send(iter) {|x|
        t = t.resume x
      }
      t.resume(eoi)
    }
  end

  def next
    @c.resume(Thread.current)
  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
------

行数を比較してみるとわかりますが、ほとんど同じです。

というわけで、

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

という主張は、やはり、単にロックを気にしなくていいというところに起因す
るのであろうという結論に至りました。

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

思うに、コルーチンでは済まない用途を模索しないと生き延びられないんじゃ
ないでしょうか。ところが、そういう

In article <[e-mail]>,
  Shin-ichiro HARA <[e-mail]> writes:

> この Thread by callcc のフレームに乗らない callcc の例を考えて
> みたのですが、こういうバックトラッキングシステムが該当するよう
> です。

というようなやつをサポートするには言語およびライブラリの手厚い支援が必
要です。

とくにライブラリは厄介で、こういうのを安全に使うには、全ての(あるいは
少なくとも大部分の)ライブラリが、常にクライアントのコードを実行したら
そこで継続を保存されて、何回も再入してくるという可能性を考慮して書かな
いといけません。これはライブラリの作者にとって負荷が高すぎ、しかも、そ
れに対して用途が少な過ぎる、というのが知合い(g新部さん)の callcc 有害
論です。

なかなか反論するのは難しいです。

理論的な意味合いで、primitive が少なくなるからよい、というのには同意し
てくれるんですが、それが実際的なプログラミングに結び付くかというとなか
なか難しいわけです。

なお、Ruby には dynamic-wind がないのでライブラリを callcc safe にする
のは難しいでしょうね。いや、あっても難しいという気はしますが。
-- 
[田中 哲][たなか あきら][Tanaka Akira]
「ふえろ! わかめちゃん作戦です$(C⊇」(Little Worker, 桂遊生丸)