|
並行制約プログラミング
並行制約プログラミング（へいこうせいやくプログラミング、英: Concurrent Constraint Programming）は、制約論理プログラミングの研究と並行論理プログラミングの研究とから生まれた、並行プログラミングのためのパラダイムである。並行制約プログラミングでは並行論理プログラミングをより一般化し、制約の出力(追加, tell)と入力(観測, ask)を行う複数のプロセス（エージェント）でプログラミングを行う。 歴史1970年代初めに生まれた論理プログラミングの考え方は、その宣言的な性格を活かしつつより表現力を大きくするため、一般的な制約を扱うように拡張され、Prolog Ⅱ(1980)やProlog Ⅲ(1987)、IBMのJafferやLassezらが1987年に発表した制約論理プログラミングスキーマCLP(X)に基づいた各種言語などに発展していった。[1] それと並行して、論理プログラミングでの導出時のゴールをプロセス、ゴール間で共有する論理変数を通信チャネルと見なす、van Emdenとde Luceanaらの論理プログラミングのプロセス的解釈（1979）[2] から、ガード付きコマンドの考えに基づいたガード付きホーン節でプロセスの生成や通信を表現する並行論理プログラミングの考え方が生まれた。ShapiroのConcurrent Prolog（1983）[3] や上田によるGHC (1985)[4] やKL1などの様々なプログラミング言語や各種のプログラミングテクニックが開発され、また第五世代コンピュータプロジェクトで並列マシンのオペレーティングシステムや言語処理系、さまざまな応用プログラムの作成に利用された。 1987年にMichael Maherはより抽象化された並行論理プログラミングの論理的解釈を与え、並行論理プログラミングでの通信と同期とを制約ストア（変数値に関する部分情報の格納場所）と受信したい情報との含意（implication）の関係として定式化した[5] 。Vijay Saraswatらはこれらの解釈を特定のデータ領域に限定しない制約全般に広げ、より一般化された並行制約プログラミングの計算理論が整備された。[6][7] 並行制約プログラミングはその後さらに拡張され、離散変化を扱う時間並行制約プログラミング（Timed Concurrent Constraint Programming）や、離散・連続の両変化を扱うハイブリッド並行制約プログラミング（Hybrid Concurrent Constraint Programming）などが生まれた。 概要並行制約プログラミングが他の多くのプログラミングパラダイムと異なる部分は、通常の手続型言語のような「値を格納」するという考え方ではなく「制約を格納」する、という考え方である。制約（例えば"X ≧ 10"）は特定の変数に対する部分情報を表している。計算中、システムの状態は制約ストア（store）と呼ばれる制約の集合で表される。プロセスは制約ストアに別の制約（例えば"X ≦ 20"）を追加（tell）することでシステムの状態を変更し、制約ストアの観測（ask）を行い与えられた制約が制約ストアの内容から導き出せるか調べることで同期と通信を行う。 プロセス計算（process calculi）の立場でみた場合、並行制約プログラミングは以下のオペレータから構成される。
例えば、並行論理プログラミングは、並行制約プログラミングをエルブラン領域(Herbrand universe)という有限木で表されるデータ領域に適用し、制約を等号制約（ユニフィケーション）のみに制限したものと見なすことができ、プログラムを以下の節の集まりで表現したものととらえることができる。 h :- ask : tell | B ここでhは原子論理式、Bは原子論理式の集まりでプロセスの並列合成を表す。ask、tellはそれぞれ制約の観測と追加の集まりである。 特徴並行制約プログラミングは以下の特徴を持つ[6]。
応用並行制約プログラミングのプロセス計算（process calculi）を応用したものとして、時間並行制約プログラミング、ハイブリッド並行制約プログラミング、線形並行制約プログラミングなどがある。また、並行制約プログラミングの様々な要素を並行プログラミングではなく制約充足系（constraint solver）の記述に用いたものとしてConstraint Handling Rules（CHR）がある。 時間並行制約プログラミング時間並行制約プログラミング（Timed Concurrent Constraint Programming）は、並行制約プログラミングを制約の離散的な変化に応用したものである。プロセス計算（process calculi）上では、並行制約プログラミングに否定情報を扱うための機能を追加したデフォルト並行制約プログラミングに、プロセスを単位時間後に起動するオペレータ("Unit Delay")を追加したものと見なすことができる。 ハイブリッド並行制約プログラミングハイブリッド並行制約プログラミング（Hybrid Concurrent Constraint Programming）は、時間並行制約プログラミングをさらに拡張して、並行制約プログラミングを離散・連続の両方向の変化で扱えるように拡張したものである。例えば、微分方程式で表せるような連続的な変化と、時間並行制約プログラミングで表せる離散的な変化とを同時に表現できるような枠組みを目指している。 プログラムはある時点(point)での処理についての記述と, ある時点から次の時点までの間(interval)の処理についての記述から構成される。連続変化と離散変化の2つのフェーズに分け、両フェーズを繰り返し実行することで整合性のある解を求める。 ハイブリッド並行制約プログラミングでは以下の3種類の制約が使われる。
ハイブリッド並行制約プログラミングは連続的な時間変化を扱うアニメーションツールなどへの応用が考えられている。 線形並行制約プログラミング線形並行制約プログラミング（Linear Concurrent Constraint Programming）は並行制約プログラミングを線形論理（Linear Logic）と呼ばれる論理体系に応用したものである。Vijay Saraswatにより1993年頃に可能性が指摘され[8]、 Francois Fagesらにより理論的にまとめられた[9]。 Constraint Handling Rules→詳細は「Constraint Handling Rules」を参照
Constraint Handling Rules（CHR）は1991年にThom Frühwirthが発表した多重集合の書換えに基づく制約処理用プログラミング言語であり[10] [11]、 主にPrologなどのホスト言語上に実装されたライブラリとして提供される事が多い。CHRは並行プログラミングではなく、さまざまな制約下での解を求める制約充足系（constraint solver）の記述を目的としている。また、通常の並行制約プログラミング言語と異なり、制約は追加(tell)ではなく書き換え(削除/追加)を行う。 CHRの特徴は以下の通りである。
CHRは単純化規則（Simplification rule）と伝播規則（Propagation rule）の2種類の規則、およびそれを組み合わせた規則（"Simpagation" rule）からなる。
H1, ..., Hi ⇔ G1, ..., Gj|B1, ..., Bk .
H1, ..., Hi ⇒ G1, ..., Gj|B1, ..., Bk . 単純化規則は、複数の制約を論理的に等価なより単純な制約に変換する。(例えば、X≦Y, Y≦X ⇔ X=Y.) 伝播規則は、論理的には冗長だが単純化に結び付くような制約を新しく追加する。(例えば、X≦Y, Y≦Z ⇒ X≦Z.) LMNtalLMNtal（Linked Multisets of Nodes transformation language、エレメンタル）はGHCの設計者である上田らによって開発された多重集合の書換えに基づく分散処理向け制約処理の言語モデルで、計算を階層的なグラフ構造の書き換えであるとした点に特徴がある[12]。 プロセスやルールは膜によってグループ化され、計算の局所化とグラフの階層化に利用される。循環構造や密に結合したデータ構造を容易に扱うことができ、またチャネルモビリティとプロセスモビリティの両方を備えている。JavaやC言語による言語処理系が開発されている。 プログラミング言語並行制約プログラミングの考え方を取り入れたプログラミング言語の例を以下に示す。 並行論理プログラミング言語Relational Language、Concurrent Prolog、Guarded Horn Clauses (GHC)とGHCの拡張であるKL1、PARLOG、Strandなどの並行論理プログラミング言語は、並行制約プログラミング言語の一種としてとらえることができる。 多くの言語はホーン節にガードを導入した形式でプログラムを記述するが、それらのガード部は制約の観測を行うask部と制約の追加を行うtell部の組み合わせとして一般化できる。 JanusJanusは、GHCなどの並行論理プログラミング言語の影響を受けてSaraswatが開発した分散処理向け制約プログラミング言語で、多重集合と配列の書換えに基づく制約処理モデルを持つ[13]。Janusの多重集合と配列とは循環を含んでよく、多重集合は無限の「超多重集合」を表現でき、配列は論理プログラミング言語での項（term）を拡張した、有限幅の無限木を表現できる。さらに、ローマ神話のヤーヌスの二つの顔のように、実行時に現れる同じ変数は2回(入力側と出力側)以下という構文的な制限があり、実行時に失敗することがない特性を持っている。Janusは並行論理プログラミング言語と同じく、ストリームに基づいたデータフロー型のプログラムを素直にプログラムできる。 また、Janusの機能を制限したLucyと呼ばれる言語でアクターモデルが自然に表現できるため、KahnとSaraswatはアクターモデルが並行制約プログラミングの特別なケースだと主張した[14] 。 AKLAKL (Andorra Kernel Language/Agent Kernel Language)は、D.H.Warrenの提案した論理プログラミングのAND並列実行とOR並列実行の統合モデルであるAndorra Modelをもとに、Jansonらが設計したマルチパラダイムのプログラミング言語である。並行処理の制御とPrologが得意とする解の探索とを同時に表現でき、また制約も扱うことができる[15]。 Oz(Mozart)OzはAKLのアイデアをもとにオブジェクト指向や関数型プログラミングなどの考え方を組み合わせたマルチパラダイムの言語モデルで、Gert Smolkaらにより開発された[16]。 いくつかのバージョンがあり、Oz 1、Oz 2、Oz 3のモデルがある。実際の言語処理系としては、Mozart Consortiumが開発したMozartプログラミングシステムがある。 脚注
参考文献
関連項目 |
Portal di Ensiklopedia Dunia
