Concurrent_Prologとは? わかりやすく解説

Concurrent Prolog

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/10/12 22:09 UTC 版)

ナビゲーションに移動 検索に移動
Concurrent Prolog
パラダイム 並行論理プログラミング
登場時期 1983年
設計者 Ehud Y. Shapiro
型付け 動的型付け
主な処理系 Logix
影響を受けた言語 Relational Language
影響を与えた言語 PARLOGGuarded Horn ClausesKL1StrandOzCHR、Janus、AKL
テンプレートを表示

Concurrent Prologは、1983年に発表された並行論理プログラミング言語である。イスラエルWeizmann研究所のEhud Shapiroにより設計された[1]。それ以前に開発されたRelational Languageをより単純化し、制限を緩めた言語で、その後の並行論理プログラミング言語に大きな影響を与えた[2][3]。また、並行論理プログラミングでの様々なプログラミング手法がConcurrent Prolog上で開発された。

概要

Concurrent PrologはPrologから派生した並行プログラミングと並列実行のためのプログラミング言語で、論理変数を介して通信を行う複数の軽量プロセスのネットワークとしてプログラムを記述する。多くの並行プログラミング言語が逐次処理言語に並行実行の機能を追加したものであるのに対して、Concurrent Prologは並行実行が基本で、並行処理を素直に記述できる。

Concurrent Prologの派生言語として、組み込み述語のみをガード部に記述できるように制限してより単純化した Flat Concurrent Prolog(FCP)がある。1983年の発表以降、Shapiroにより様々なFCPのバリエーションが提案され、分析されている[4]

Concurrent Prologではホーン節ガードを導入した以下のような規則(Clause)の集まりでプログラムを記述する。"|"はコミット演算子と呼ばれる。G はガード部、B はボディ部と呼ばれる。Head、G、Bはそれぞれ原子論理式である。ガード部の条件がない場合、ガード部とコミット演算子は省略できる。

Head :- G1, ..., Gn| B1, ..., Bm.  (n,m≧0)

Headとガード部はプロセス書き換えのための条件、ボディ部は書き換え後のプロセスを表す。生成されたプロセスは全て並行に実行される。また、各プロセスごとの書き換え条件のチェックも複数の節で並行に実行してよく、コミット時にただ1つの節が選択される(コミッティッド・チョイス)。Prologと異なりバックトラックの機能はない。

プロセス間の通信にはプロセス間で共有する論理変数を使用する。多くの場合、プロセス間の通信には論理変数を含んだリストで表現されたストリームを用いる。ストリームは [<メッセージ>|<変数>] のようなリストで実現する。 論理変数を共有するプロセスの数に制限はないため、ストリーム通信は1対1だけではなく1対Nのブロードキャストなど、様々な形態が可能である。

簡単なプログラム例を以下に示す。2本のストリームをマージして1本のストリームにするプログラムで、Prologと同様、A や Xs など英大文字や"_"で始まる項は変数を表す。mergeの最初の2引数が入力ストリーム、最後が出力ストリームである。

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.

Concurrent Prologでは、プロセス間の同期のための中断のメカニズムとして読み出し専用標記 (Read Only Annotation)を用いる。読み出し専用標記は"?"で表され、任意の変数に付与することができる。読み出し専用標記が付加された変数へのアクセスは入力モードだけが許され、読み出し専用変数を変数以外の項に具体化しようとする試みは中断させられる。つまり、これにより変数が具体化されるまで待つという同期と、変数毎のデータ入出力の方向性の指定とができる。例えば、上記プログラムの最初の節では、最初の引数が[A|Xs]のようなリストの形になっていない場合は中断し、他のプロセスにより[A|Xs]の形に具体化された(具体的に値が決まった)場合に実行を再開する。この時点でXs自体は具体化されていなくても構わないため、リストの先頭からインクリメンタルに具体化されるストリームを素直に処理できる。

また、ガードの実行(ヘッドとガード部の実行)で行われた変数への書き込みは、その後の失敗により変更される可能性があるため、どれか1つの節がコミットされるまで他のプロセスに公開されない。例えば、上記マージプログラムの最初の節での [A|Zs] と2番目の節での [A|Zs] とは値が異なる可能性がある。Concurrent Prologでは、ガード実行時に節ごとで変数の値が異なる多重環境を管理する必要があり、全ての節の並行実行を行う際に管理が複雑になる。

プログラム例

以下にConcurrent Prologのプログラム例を示す。

待ち行列

FIFO待ち行列を管理するプログラムの例を以下に示す。ストリームSに enqueue(X) のメッセージを送るとXの内容が待ち行列の最後に追加され、dequeue(X) のメッセージを送ると待ち行列の先頭要素がXに返される。待ち行列の表現には、2つのリストの差分で1つのデータの並びを表現する差分リストのテクニックが使用されている。

queue(S) :- queue(S, Z, Z).

queue([dequeue(X)|S], [X|NewHead], Tail) :- queue(S?, NewHead, Tail).
queue([enqueue(X)|S], Head, [X|NewTail]) :- queue(S?, Head, NewTail).
queue([], _, _).

前出のマージプロセスと組み合わせることで、複数のプロセスからの dequeue/enqueue のメッセージを処理することができ、クライアントサーバモデルでのサーバプロセスのように使うことができる。

素数生成

エラストテネスのふるいを使い素数生成を行うプログラム例を示す。

gen_primes(Max,Primes) :- integers(2,Max,Ns), sift(Ns?,Primes).

gen_primes/2を実行すると、integers/3とsift/2の2つのプロセスが生成される。integers/3はMaxまでの自然数のストリームを生成し、sift/2はそれをふるいにかけ素数のストリームをPrimesに返す。integers/3とsift/2とはそれぞれ並行して動き、integers/3で生成された自然数のストリームは変数Nsを介して順次sift/2に渡される。読み出し専用標記により変数Nsによるintegers/3からsift/2へのデータフローの方向が表現され、プロセス間の同期はストリームの各要素が具体化されるまで待つという形で自然に表現される。

integers/3、sift/2の各プログラムはそれぞれ以下のようになる。integers/3は、自然数のストリームを順次生成しMaxを超えたら終了する。sift/2は、2,3,5,7,..などの各素数の倍数をストリームから取り除くfilterプロセス(ふるい)を順に生成しながら、求まった素数を順次ストリームの要素として返す。各filterプロセスは変数を介して直列につながれていくため、自然数のストリームから素数のみのストリームを求めることができる。

integers(N0,Max,[N0|Ns1]) :- N0=<Max, N1 is N0+1 | gen(N1,Max,Ns1).
integers(N0,Max,[]      ) :- N0 >Max             | true.

sift([Prime|Xs1],[Prime|Zs1]) :- filter(Prime,Xs1?,Ys), sift(Ys?,Zs1).
sift([],         []).

filter(Prime,[X|Xs1],[X|Ys1]) :- 0 is X mod Prime | filter(Prime,Xs1?,Ys1).
filter(Prime,[X|Xs1],Ys0    ) :- otherwise        | filter(Prime,Xs1?,Ys0).
filter(_,    [],     []).

応用

Logix

Flat Concurrent Prolog(FCP)の開発環境として、UNIXシェル風の機能とコンパイラ、デバッガを組み合わせたLogixと呼ばれるシステムが作成された。Logix自身もFCPを使って記述され、C言語で作成されたエミュレータ上で動作する。Logixで使用できる言語は、 FCP(:,?) と呼ばれるFCPの中で最も表現力の高いバリエーションに、プログラムを見やすくするための糖衣構文を付加したものである[5]。また、Guarded Horn Clausesのフラット版である Flat GHC のエミュレーション機能も含む[5]

関連項目

参考文献

  • Clark, K, L. and Gregory, S. PARLOG: a parallel logic programming language. Research Report DOC 83/5, Imperial College, London. 1983.
  • Shapiro, E. A subset of Concurrent Prolog and its interpreter. ICOT Tech. Rep. TR-003,ICOT, Tokyo. 1983.
  • Shapiro, E.. The Family of Concurrent Logic Programming Languages. ACM Computing Surveys, Vol.21, No.3, September 1989.
  • Ueda, K. Guarded Horn Clauses. ICOT Technical Report TR-103, ICOT, Tokyo. 1985.
  • Ueda, K. Guarded Horn Clauses. Doctoral Thesis. Information Engineering Course, University of Tokyo, 1986 (PDF)
  • Silverman, W., Hirsch, M.,Houri, A. and Shapiro, E. The Logix System User Manual Version 2.0. Technical Report CS-21, Weizmann Institute of Science, 1993
  • Silverman, W., Hirsch, M.,Houri, A. and Shapiro, E. Logix Supplement to User Manual for System 2.2. Weizmann Institute of Science, 1990.
  • 古川 康一,溝口 文雄(編), 並列論理型言語GHCとその応用 (知識情報処理シリーズ). 共立出版 1987, ISBN 978-4320022669
  • 竹内 彰一, 論理型並列プログラミング言語 : Concurrent Prolog. コンピュータソフトウェア Vol.1 No.2 pp.131-143 1984.
  1. ^ Shapiro, E. A subset of Concurrent Prolog and its interpreter
  2. ^ Clark, K, L. and Gregory, S. PARLOG: a parallel logic programming language
  3. ^ Ueda, K. Guarded Horn Clauses
  4. ^ Shapiro, E. The Family of Concurrent Logic Programming Languages
  5. ^ a b Silverman, W Logix Supplement to User Manual for System 2.2

外部リンク


Concurrent Prolog

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/10/03 01:23 UTC 版)

並行論理プログラミング」の記事における「Concurrent Prolog」の解説

Relational Language参考にして、Shapiroは1983年に単純で表現力の高いConcurrent Prologを提案した通信にはストリームだけでなく任意の項が使えるようになり、ガード記述制限なくなった。不完全メッセージなどの技法も使うことができ、通信チャネル第一級オブジェクトとして扱えるようになったまた、Relational Language並行実行逐次実行両方機能含んでいたが、Concurrent Prologは全て並行実行することを前提にすることで非常に単純化され仕様になった。Concurrent PrologはShapiroにより様々なバリエーション提案され分析されている。2つストリームマージ1つストリームにするマージプロセスのプログラム例を以下に示す。 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. Concurrent Prologでは、中断メカニズムとして読み出し専用標記 (Read Only Annotation)を用いる。読み出し専用標記は"?"で表され任意の変数付与することができる。読み出し専用変数変数以外の項に具体化しようとする試み中断させられる。つまり、読み出し専用標記付加され変数へのアクセス入力モードだけが許される。これにより変数具体化されるまで待つという同期と、変数毎のデータ入出力方向性指定とができる。また、ガード実行(ヘッドガード部実行)で行われた変数への書き込みは、その後失敗により変更される可能性があるため、どれか1つの節がコミットされるまで他のプロセス公開されない。つまりConcurrent Prologのガードには制約追加を行うTell部(Atomic Tell)が含まれる。Concurrent Prologでは、ガード実行時に節ごとで変数の値が異な多重環境管理する必要があり、全ての節の並行実行を行う際に管理複雑になる言語の特徴を以下にまとめる。 * 同期表現方法 読み出し専用標記 (変数単位指定)* 制約入出力 Blocking AskAtomic Tell* プロセス間通信 任意の項を使用可能* 実行形態 並行実行* その他の特徴 言語仕様が単純、多重環境管理が必要、Atomic Tellにより表現力が高い

※この「Concurrent Prolog」の解説は、「並行論理プログラミング」の解説の一部です。
「Concurrent Prolog」を含む「並行論理プログラミング」の記事については、「並行論理プログラミング」の概要を参照ください。

ウィキペディア小見出し辞書の「Concurrent_Prolog」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



固有名詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「Concurrent_Prolog」の関連用語

Concurrent_Prologのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Concurrent_Prologのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのConcurrent Prolog (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの並行論理プログラミング (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS