Lindaのeval()の話（MinRuby編）

はじまり

MinRubyならコンテキスト（tree, genv, lenv）もRubyオブジェクトだからdRubyで飛ばせるじゃん。
なにかいい使い道はないものか...

並列プログラムの作り方

C-Lindaのeval()

このブログを見てる人たちにはおなじみのタプルスペースの話。
Lindaの操作はoutとin, rd、そしてプロセスを起動するevalです。outはタプルをタプルスペースに書きます。inはパターンで指定したタプルを取り出します（タプルスペースから取り除かれます）。rdはinと同様ですが読むだけでタプルスペースは変化しません。inp, rdpは待ち合わせをしないバージョンのinとrdです。*1

最後のevalが曲者で、実引数の評価（計算？）を別プロセスで行い、全ての実引数の評価結果から成るタプルをタプルスペースに書きます。evalをコールした側には直ちに制御が戻ります。つまり同時にN個のプロセスを生成し、それぞれの結果を待ち、その結果をタプルスペースに書くこと別プロセスが生まれるのです。これって相当ゴージャスな感じがします！

以下、C-Lindaの擬似コード。
なんらかのサーバーを起動するならこんなの。server()という関数を実行するプロセスが一つ生成されます。

  eval(sever());

なにかの演算をさせておくならこんなの。"fib"と100とfib(100)を評価するプロセスが三つ生成されて、全てが終わるとタプルを書きます。

  eval("fib", 100, fib(100));
  /* .... */
  in("fib", 100, ?result);

こういうのも動くはず。

  eval("eval", a + b,  c * d, fib(1000), prime(200));

Nプロセスで格子状の計算をするならこう。

  for (i = 0; i < N; i++) {
    eval("row", sum_of_row(i + 1));
  }

  total = 0;
  for (i = 0; i < N: i++) {
    in("row", ?sum);
    total += sum;
  }

Rindaのeval

Ruby版LindaことRindaには標準にはevalがありませんが、MoreRindaを使うと、rinda_evalが追加されます。

• https://github.com/seki/MoreRinda/
• http://druby.hatenablog.com/entry/20110519/rinda_eval

10.times do |n|
  # placeはタプルスペース。ブロック引数が子プロセスで実行され、その結果はplaceにwriteされる。
  # サブプロセス側からは、親プロセスのタプルスペースはtsという仮引数で操作できる。
  Rinda::rinda_eval(place) do |ts| 
    [:sqrt, n, Math.sqrt(n)]
  end
end

Rubyでは実引数は呼び手のコンテキストで評価された後に渡されますから、C-Lindaのeval()のような見た目にはなりません。
代わりにブロック引数をforkした子プロセスに実行させることにしました。機能としては同じようなことができますが、見た目がだいぶ違います。
これじゃforkのラッパーにしか見えませんね。ぐぬぬ。

MinRubyでeval

RubyでつくるRuby ゼロから学びなおすプログラミング言語入門

そこでMinRubyです！こちらはインタプリタの挙動を好きなように変えられます。くくく。
並列処理糊言語であるLinda、そのRuby実装Rinda、そしてMinRubyをRindaを使ったアプリケーション専用の糊言語にしてしまえ！

• インタプリタ自身がインタプリタを実行できる機能（ブートストラップ）は、一旦忘れる
• インタプリタは（ひとまずは固定のURI）Rinda::TupleSpaceサーバーのクライアントとして動く
• 実装するプリミティブは、 write, read, take, eval だけ
• evalで生成される（仮想的な）プロセスは、（UNIXな）ワーカープロセスで実行する
• evalで評価させる内容はタプルとしてタプルスペースに書く（tree, genv, lenvはMarshal可能なRubyオブジェクトなので安心）

write, read, takeはpと同様に普通のbuiltinメソッドとしてgenvに登録すればいい。
問題はevalです。evalは評価方法を変えたいのでifやwhileみたいなスペシャルフォームにしたいところだけど、min_ruby改造するのもアレなので、とりあえずメソッド種にbuiltinとは別のマークをつけることにしました。

    genv = {
      "p" => ["builtin", "p"],
      "eval" => ["x-builtin", "nop"],
      "go" => ["g-builtin", "nop"], # これはいまは気にしない
      "read" => ["builtin", "ts_read"],
      "take" => ["builtin", "ts_take"],
      "write" => ["builtin", "ts_write"]
    }

func_callで種類がx-builtinのとき、関数コールではなくプロセス生成に変更します。

    when "func_call" 
      mhd = genv[tree[1]]
      case mhd[0]
      when "x-builtin"
        args = []
        i = 0
        while tree[i + 2]
          args[i] = tree[i + 2]
          i = i + 1
        end
        minruby_call(mhd[1], x_evaluate(args, genv, lenv))

実引数をevaluateせずにtreeのまま集めて、genvとlenvと一緒に x_evaluate メソッドに渡します。
現在の実装ではこのあたりからブートストラップ不可能になっていきます。残念。

x_evaluateは実行コンテキスト（tree, genv, lenv）をタプルスペースに書きます。これがワーカーへの指示になります。
その後、ワーカーが書く予定の結果のタプルをtakeして全ての引数分の結果が集まったら、それをタプルスペースに書きます。

  def x_evaluate(args, genv, lenv)
    keys = args.collect do |tree|
      case tree[0]
      when "lit" # リテラルは特別扱いしたけど、もしかすると変数参照も特別扱いするべきかも。
        tree
      else
        key = [tree, genv, lenv].hash
        $ts.write([:x_eval, @node, key, tree, genv, lenv])
        [key]
      end
    end

    Thread.new(keys) do |ks|
      tuple = ks.collect do |tree_or_key|
        case tree_or_key[0]
        when "lit"
          tree_or_key[1]
        else
          _, _, _, value = $ts.take([:x_eval, @node, tree_or_key[0], nil])
          value
        end
      end
      $ts.write(tuple)
    end

    true
  end

ワーカーに処理を依頼するタプルは次のように設計しました。

[:x_eval, @node, key, tree, genv, lenv]
[:x_eval, @node, key, nil]

:x_evalはタプルのおおまかな識別子。@nodeはプロセス固有の乱数です。
keyはコンテキストのハッシュ値です。まあ偶然ぶつかっちゃうかもしれないけど、今は実験だから気にしない。連番でも乱数でもいい。
genvを渡すってことは、定義されている関数全部飛ぶってことなので、けっこうゴージャスだ！

以下は10年前に情報処理に載せたNQueens問題をMinRubyで書き直したやつ。return使えないのツライ。

def check(size, board, q, col)
  k = 0
  succ = true
  while k < col
    case board[k] - q
    when 0
      succ = false
      k = col
    when col - k
      succ = false
      k = col
    when k - col
      succ = false
      k = col
    else
    end
    k = k + 1
  end
  succ
end

def nq(size, board, col)
  if size == col
    1
  else
    found = 0
    q = 0
    while q < size
      if check(size, board, q, col)
        board[col] = q
        found = found + nq(size, board, col + 1)
      else
      end
      q = q + 1
    end
    found
  end
end

def nq2(size, q)
  if check(size, [], q, 0)
    nq(size, [q], 1)
  else
    0
  end
end

size = 10
n = 0
while n < size
  eval("nq2", nq2(size, n))
  # nq2()の実行は別プロセスで行われる。
  # なお、nq2とnqとcheckの関数定義もコピーされちゃうぞ！
  n = n + 1
end
n = 0
found = 0
while n < size
  tuple = take("nq2", nil) # evalの結果を待つ。順序に意味がないのでおわった順に集める。
  p tuple
  found = found + tuple[1]
  n = n + 1
end
p found

まあ動く！ワーカー増やすと速くなる！！ふつう！！！

書いてて飽きてきた！続きはまた今度！！