PARLOG
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/04/16 10:13 UTC 版)
| パラダイム | 並行論理プログラミング |
|---|---|
| 登場時期 | 1983年 |
| 設計者 | Keith Clark、Steve Gregory |
| 型付け | 動的型付け |
| 主な処理系 | PARLOG for Windows, 他 |
| 影響を受けた言語 | Prolog、Relational Language、Concurrent Prolog、Guarded Horn Clauses |
| 影響を与えた言語 | Guarded Horn Clauses、KL1、Strand、PCN |
PARLOG (PARallel LOGic) は、Concurrent Prologに影響を受けたKeith ClarkとSteve Gregoryにより設計された並行論理プログラミング言語である。複雑なRelational Languageの仕様を整理した後継言語として提案された。1983年に最初のバージョンが発表され、その後1986年に改良版が発表された。言語の特性や細かいシンタックスはそれぞれ異なる。
概要
PARLOGは並行プログラミングのためのプログラミング言語で、論理変数を介して通信を行う複数の軽量プロセスのネットワークとしてプログラムを記述する。 PARLOGではホーン節にガードを導入した以下のような規則の集まりでプログラムを記述する。":"はコミット演算子と呼ばれる。ガード部がない(Guardでの条件が"true"のみ)場合、ガード部とコミット演算子は省略できる。
Head <- Guard : Body.
HeadとGuardはプロセス書き換えのための条件、Bodyは書き換え後のプロセスを表す。条件を満たす規則が複数ある場合はどれか1つが選択される。Prologなどと異なり、コミット後のバックトラックを行わない。Body部は逐次/並行の2通りの実行方法が指定できる。
- p , q 並行AND：p,qを並行実行
- p & q 逐次AND：p,qを逐次実行(pが成功した場合のみqを実行)
例えば、 (p, q) & r は、p と q を並行に実行し、両者が成功したとき r を実行する。
プロセス間の通信にはプロセスで共有する論理変数を使用する。書き換え規則の適用に十分な情報がなければ書き換えを中断し、判断に必要な情報が得られるまで待つことで、プロセス間の同期が行われる。多くの場合、プロセス間の通信には論理変数を含んだリストで表現されたストリームを用いる。論理変数を共有するプロセスの数に制限はないため、ストリーム通信は1対1だけではなく1対Nのブロードキャストなど、様々な形態が可能である。
それぞれの述語には入出力のモード宣言が付加される。"?"は入力モード、"^"は出力モードを表す。ヘッド部の同一化の際、アクセスモードが入力モードに指定されている引数は入力のみができ、呼び出し側の変数を変数以外の項に具体化しようとする試みは中断させられる。出力モードとして指定された項が実際に出力されるのは節が選択された後である。
プログラム例
1983年版のPARLOGと1986年に改良されたPARLOGとでは、言語の特性や細かいシンタックスがそれぞれ異なる。 1983年版PARLOGのプログラムの例を以下に示す。 append(x, y, z)は x と y の2つのリストを連結したリストが z であるという関係を表している。Prologと異なり、英小文字で始まる項が変数を表す。relationはモード宣言を示し、複数の組み合わせを指定できる。
relation append(?,?,^)
relation append(?,^,?)
relation append(?,?,?)
append([], y, y).
append([u|x], z, [u|z]) :- append(x, y, z)
1986年版では複雑だった言語仕様を整理し、より効率的な実行が可能になった。1986年版PARLOGのプログラムの例を以下に示す。Prolog同様、英大文字で始まる項が変数を表す。 merge(Xs?,Ys?,Zs^)はXsとYsの2本のストリームをマージして1本のストリームZsにする。modeはモード宣言を示し1述語に1つのみ指定できる。
mode merge(Xs?,Ys?,Zs^).
merge([A|Xs],Ys,[A|Zs]) <- merge(Xs,Ys,Zs).
merge(Xs,[A|Ys],[A|Zs]) <- merge(Xs,Ys,Zs).
merge([],Ys,Ys).
merge(Xs,[],Xs).
PARLOGによるプロセス間の同期の機能は、kernel PARLOGというモード宣言を持たない単純な標準形式に変換することで実現された。PARLOGでモード宣言が果たしていた役割は、特殊な単方向のユニフィケーションを入力側はガード部に、出力側はボディ部に付加することで実現され、ガード部で中断が行われる。例えば、上記プログラムの最初の節はkernel PARLOGで以下の形式に変換された。
merge(X,Ys,Z)<-
[A|Xs] <= X : Z = [A|Zs] ,merge(Xs,Ys,Zs).
<= は一方向のユニフィケーションを表し、Xが[A|Xs]のようなリストの形になっていない場合は中断し、他のプロセスにより[A|Xs]の形に具体化された場合に実行を再開する。この時点でXs自体は具体化されていなくてもかまわないため、リストの先頭からインクリメンタルに具体化されるストリームを素直に処理できる。
関連項目
参考文献
- Clark, K. L., and Gregory, S. A relational language for parallel programming. In Proceedings of the ACM Conference on Functional Languages and Computer Architecture. ACM. 1981.
- Clark, K, L. and Gregory, S. PARLOG: a parallel logic programming language. Research Report DOC 83/5, Imperial College, London. 1983.
- Clark, K. L., and Gregory, S. PARLOG: Parallel programming in logic. ACM Trans. Program. Lang. Syst. 8, 1, l-49, ACM. 1986.
- Shapiro, E.. The Family of Concurrent Logic Programming Languages. ACM Computing Surveys, Vol.21, No.3, September 1989.
PARLOG
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/03 01:23 UTC 版)
「並行論理プログラミング」の記事における「PARLOG」の解説
PARLOG (PARallel LOGic) は、Concurrent Prologに影響を受けたClarkとGregoryにより、複雑なRelational Languageの仕様を整理した後継言語として提案された。1983年に最初のバージョンが発表され、その後1986年に改良版が発表された。言語の特性や細かいシンタックスはそれぞれ異なる。PARLOGはRelational Languageと同様、並行実行と逐次実行の両方の機能を持っており、言語仕様はConcurrent PrologやGHCと比べて複雑である。1986年版でのマージプロセスのプログラム例を以下に示す。":"はコミット演算子を表す。 mode merge(Xs?,Ys?,Zs^).merge([A|Xs],Ys,[A|Zs]) <- true : merge(Xs,Ys,Zs).merge(Xs,[A|Ys],[A|Zs]) <- true : merge(Xs,Ys,Zs).merge([],Ys,Ys) <- true : true.merge(Xs,[],Xs) <- true : true. PARLOGでは、中断のメカニズムとしてモード宣言を用いる。"?"は入力モード、"^"は出力モードを表す。ヘッド部の同一化の際、アクセスモードが入力モードに指定されているゴール中の変数を変数以外の項に具体化しようとする試みは中断させられる。また、出力モードとして指定された項が実際に出力されるのは節が選択された後である。PARLOGの機能はkernel PARLOGというモード宣言を持たない単純な標準形式に変換することで実現される。PARLOGでモード宣言が果たしていた役割は、特殊な単方向のユニフィケーションを入力側はガード部に、出力側はボディ部に付加することで実現され、ガード部で中断が行われる。kernel PARLOGでのガードの規則はGHCの規則と同じ意味を持つ。kernel PARLOGのガードには制約の追加を行うTell部がなく制約の観測を行うAsk部のみのため、多重環境の問題はない。kernel PARLOGに変換できないプログラムをエラーとすることでAsk部のみであることを保証する。kernel PARLOGに変換できるPARLOGプログラムの出力モードは入力可能として扱われ、不完全メッセージなどの技法も使用できる。ただしガード部の安全性のチェックをコンパイル時に行っているため、Concurrent PrologやGHCでは数行で書ける自分自身のメタインタプリタをPARLOGでは素直に書くことができない。言語の特徴を以下にまとめる。 * 同期の表現方法 モード宣言(制限を緩和) (述語単位で指定)* 制約の入出力 Blocking AskとEventual Tell* プロセス間通信 任意の項を使用可能* 実行形態 並行実行と逐次実行* その他の特徴 ガードの安全性をコンパイル時にチェック、言語仕様が複雑で多機能、多重環境の管理が不要
※この「PARLOG」の解説は、「並行論理プログラミング」の解説の一部です。
「PARLOG」を含む「並行論理プログラミング」の記事については、「並行論理プログラミング」の概要を参照ください。
- PARLOGのページへのリンク
