Lindaのeval

Lindaにはevalっていう操作があって、名前に反してプロセスを起動するんだよね。
タプルの各要素の数だけプロセスを生成し、要素の式を新しいプロセスで評価します。んで、すべてのプロセスが終了したらタプルを一つ追加します。例えば

  eval("fib", 10, fib(10))

だと"fib"を返すプロセス、10を返すプロセス、fib(10)を計算して返すプロセスの三つを生成して全てが終了したらタプルスペースに一つのタプルを追加する。

サブセット版のevalでは、要素ごとにプロセスを生成するのではなく、一つだけってこともあるみたい。

で、いまはRindaにevalがないのはポータブルなプロセス起動の仕組みが思いつかなかったから。試しにUNIX類限定で作ってみよう。

require 'drb/drb'
require 'rinda/rinda'

module Rinda
  class TupleSpace
    def rinda_eval(&blk)
      Rinda::rinda_eval(self, &blk)
    end
  end

  class TupleSpaceProxy
    def rinda_eval(&blk)
      Rinda::rinda_eval(@ts,  &blk)
    end
  end

  module_function
  def rinda_eval(ts)
    ts = DRbObject.new(ts) unless DRbObject === ts
    fork do
      DRb.stop_service
      DRb.start_service('druby://localhost:0')
      place = TupleSpaceProxy.new(ts)
      begin
        tuple = yield(place)
        place.write(tuple)
      rescue DRb::DRbConnError
        # NOP
      end
    end
  end
end

if __FILE__ == $0
  require 'rinda/tuplespace'

  DRb.start_service('druby://localhost:0')
  place = Rinda::TupleSpace.new
  place.rinda_eval do |ts|
    sleep 1
    [:hello, Time.now]
  end
  p place.take([:hello, nil])
end

IPSJの記事のために書いたNQueenをライブタプルで書き直すとこう。

require 'rinda/tuplespace'
require 'rinda_eval'
require 'nq'

DRb.start_service('druby://localhost:0')
rinda = Rinda::TupleSpace.new
size = (ARGV.shift || '5').to_i

size.times do |r1|
  size.times do |r2|
    rinda.rinda_eval do |ts|
      [:nq_ans, size, r1, r2, NQueen.nq2(size, r1, r2)]
    end
  end
end

found = 0
size.times do |r1|
  size.times do |r2|
    tuple = rinda.take([:nq_ans, size, r1, r2, nil])
    p tuple
    found += tuple[4]
  end
end
puts found

最初のループのrinda_evalはたくさんのプロセスを起動します。
Linuxは動いたけどOSX(省電力モード)だとコネクションがはれなくて動かなかった。気持ちはわかるけど‥。
(追記) localhost:0をやめたら(TCP/IPにしたら)うまく動くようになったぞ。

現実的な解はこうかな。4つのエンジンで解く場合の例。　

require 'rinda/tuplespace'
require 'rinda_eval'
require 'nq'

DRb.start_service
rinda = Rinda::TupleSpace.new
size = (ARGV.shift || '5').to_i

size.times do |r1|
  size.times do |r2|
    rinda.write([:nq, size, r1, r2])
  end
end

4.times do
  rinda.rinda_eval do |ts|
    while true
      sym, size, r1, r2 = ts.take([:nq, Integer, Integer, Integer])
      ts.write([:nq_ans, size, r1, r2, NQueen.nq2(size, r1, r2)])
    end
    [:nq_engine]
  end
end
  
found = 0
size.times do |r1|
  size.times do |r2|
    tuple = rinda.take([:nq_ans, size, r1, r2, nil])
    found += tuple[4]
  end
end
puts found

前にも書いたけどnq.rbは次の通り。

module NQueen
  module_function
  def concat(board, row)
    board.each_with_index do |v, col|
      check = (v - row).abs
      return nil if check == 0
      return nil if check == board.size - col
    end
    board + [row]
  end

  def nq(size, board=[])
    found = 0
    size.times do |row|
      fwd = concat(board, row)
      next unless fwd
      return 1 if fwd.size == size
      found += nq(size, fwd)
    end
    found
  end

  def nq2(size, r1, r2)
    board = concat([r1], r2)
    return 0 unless board
    nq(size, board)
  end
end