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;
}
MinRubyでeval
そこで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))
n = n + 1
end
n = 0
found = 0
while n < size
tuple = take("nq2", nil)
p tuple
found = found + tuple[1]
n = n + 1
end
p found
まあ動く!ワーカー増やすと速くなる!!ふつう!!!
書いてて飽きてきた!続きはまた今度!!