Help us understand the problem. What is going on with this article?

Erlang上でP-GHCの夢

ArcSoft_画像218.PNG

はじめに

いつかGHCを作ってみたいという思いがありました。ラズパイ・クラスタマシンを作って、そこで並列に動作するGHCです。処理系の名前はP-GHCです。夢みたいな話かなぁと思っていたら、夢でもなさそうな気配になってきました。そのあたりのことを書きとめようと思います。なお、私は現時点でGHCのことを勉強中であり、理解不足の点も多々あろうかと思います。誤っている点は編集リクエストをいただければ幸いです。

GHCとは

1980年代に上田和紀先生が設計した並列Prologです。コードはこんな風になります。

concat([A|X1],Y,[A|Z1]) :- true |
     Z=[A|Z1],concat(X1,Y,Z1).
concat([],Y,Z) :- true | Z=Y.

ガード付きホーン節といいます。GHCの由来はこのguarded Horn Clause です。
','はPrologと同様に連言です。
’'|'はコミット演算子といいます。

逐次処理のPrologとなんとなく似ているようなシンタックスですが、動作はかなり違います。その詳細は後ほど。

並列の時代

先日、Erlangとその応用のElixirに出会い、勉強していました。計算実験をしつつ軽量プロセスを多数生成することができることがわかりました。ひょっとしErlangの軽量プロセスを利用すればGHCを実装できるのではないか?と思いました。

実は2年ほどまでにプロジェクトP子ちゃん(すみません、ふざけたネーミングで)を思いつきました。当時、ラズパイをいじくっておりこれでクラスタマシンを作って並列処理のGHCを動かしたら面白いと思いました。自分の実力を完全に無視した壮大な計画でした。あれからO-Prologの改良に忙しく、まだまだGHCやクラスタマシンには取り掛かれていません。最近、Erlangのことを知り、ひょっとしてラズパイクラスタマシンを作らなくてもErlangで普通のパソコン上で並列処理ができるのではないだろうか?と思いました。

並列処理動作の詳細

上田先生のGHC入門を何回も読んでみました。なかなか難解でしたが、なんとなくイメージがつかめてきました。GHCの名前の由来である Guarded Horn Clause にそのアイディアが詰まっているようです。節の各部の名称は次の通りです。

(本より引用)
ArcSoft_画像213.PNG

Prologと違ってガードというものが節の左側につけられています。concat/3の例では頭部の次にtrueが付いています。必ずここに述語が入ることになっています。trueなので成功するのですけど,
ガード部のゴールが空であることを明示するのに用いられています。ここに条件を表す述語が入る場合もあります。ガード部のゴールが全部、成功したらば | コミット演算子以後のゴールを並列に実行します。

並列に実行する規則は下記の2つです。上田先生の記述をそのまま引用します。

引用
(1)節のガードは、受動的に、すなわちその呼び出し側を具体化することなく実行しなければならない。

(2)節のボディーは、その節の呼び出し側を具体化してもよいが、それが許されるのは各呼び出しごとにただひとつの節に限られる。

引用終わり

う~むむ、難解です。わかりません。(1)の規則は具体例だとこんな風です。

ArcSoft_画像214.PNG

Prologだと述語の真偽を実行するのに普通、?- を使うのですが、GHCでは :- を使うのが通例みたいです。ともかく、concat/3を :- concat(U,[4,5],W). と呼び出すのはまずいんですね。逐次処理のPrologなら問題ないのですけど。Uはまだ具体化されていないので、(1)の規則により実行できません。この場合は中断します。待つのですね。いつまで待つの?

(本より引用)
ArcSoft_画像215.PNG

ゴールが連言になっています。concat/3のときにはUはまだ具体化されていませんが、そのあとのU=[1,2,3]でUが具体化されています。こういう状態になったら中断は解除されてガード部が成功します。

(2)の規則ですが、要するに1つしか実行する節は選べないんですね。|コミット演算子を通過すると、以後のゴールをバラバラに並列に実行します。複数の節がある場合には(1)の規則を満たすかどうかをを片っ端から動作、確認します。でも1つの節しか選べません。どうやって選ぶのか?

基準はありません。通常は最初にガードの実行が成功した節を選ぶのだそうです。早いもの勝ちです。

実装してみればどうしてこういう規則にしているのかわかるのかもしれません。いったい、どういう風に動作するものなのでしょうね。

コンパイル方式

考えている実装方法はPrologでGHCのコードをErlangのコードに変換する方式です。GHCはPrologの構文とほぼ同じです。それなら一部、演算子を定義してPrologのread/1を使えばわりと簡単にパースできると思います。さらにそこにメッセージのやりとりを付加したErlangコードに変換してファイル出力、Erlangにて読み込むという方法です。

Erlangへの変換のアイディア

で、どういうErlangのコードに変換すればいいものでしょう。ぼんやり考えているアイディアは次のようです。

ArcSoft_画像216.PNG

GHCの述語はErlangの関数に変換します。複数の節がある場合にはそれらの節の全部を含みます。プロセスAが起動すると、こんどは節を関数にしたプロセスB1,B2・・・として起動します。

B1,B2・・・のプロセスはガード部を実行します。中断するものもあるでしょうし、成功するものでも、早いものも遅いものもあるでしょう。終わったものからプロセスAに終わったというメッセージを返します。

プロセスAは最初にレシーブしたプロセスに対してコミット演算子以後のゴールを述語ごとにプロセスにして並列に実行せよ、というメッセージを送ります。選択されたBプロセスはゴールが全て成功したら終わったというメッセージをプロセスAに返します。プロセスAは呼び出しもとのプロセスに計算が終わったというメッセージを返します。

最初にレシーブしたもの以外のプロセスに対しては、もう実行しなくてもいいぞというメッセージを送り終了させます。

こんなアイディアです。

共通変数

foo(X,Y),boo(Y).

このような連言のゴールがある場合、変数Yが具体化されるまではfooは中断しないといけません。booの計算が終わったら変数Yが具体化したことをfooに知らせないといけません。どうしましょうか? 共通変数を予め調べておいて、プロセスから返答がありその共通変数が具体化した場合には改めてメッセージを送ろうと考えています。なんだかややこしそうです。

再帰

逐次処理のPrologでは再帰のためのメカニズムがめんどうでした。同じ変数Xでも再帰の都度、別な変数に付け替えていました。述語をプロセスとして起動する方法であれば再帰しても別なプロセスですから、変数も別に扱われます。この点は逐次処理のPrologよりは簡単に済みそうな感じがします。

再帰する都度、プロセスを生成していたのでは時には数万プロセスになります。大丈夫なのか? Erlangなら問題ありません。軽量プロセスだからです。Elixirでの計算実験で数万、数十万個のプロセスを起動させたことがあります。涼しい顔をして計算を終了します。たぶん、大丈夫でしょう。

やってみなはれ

自作のO-Prologの実装のときもそうでした。わからないなら、まずは手を動かしてみる。何しろ、Prolog実装の文献はほとんどありません。そして実用速度で動作させようとするとそのノウハウは自分で習得するほかありませんでした。

GHCの実装はSWI-Prolog用に書かれたものが上田研究室から配布されているくらいしか見当たりません。

       作ったらエエのよ!

そう、私はいつもイージー。GHCコードをO-Prologでパース、変換してErlangコードにします。そして並列実行させます。夢ですね。いつか夢は叶うもの、なんとかなるでしょう。何年かかるかな。

参考文献

並列論理型言語GHCとその応用 淵一博 慣習 古川康一、溝口文雄 共編

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away