並行制約プログラミング

提供: miniwiki
移動先:案内、検索

並行制約プログラミング（へいこうせいやくプログラミング、英: 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）の立場でみた場合、並行制約プログラミングは以下のオペレータから構成される。

  • 追加（tell）：制約を追加する
  • 観測（ask）：制約が制約ストアから導き出せるか問い合わせる
  • 並列合成（Parallel Composition）：プロセスを並行に組み合わせる
  • 隠蔽（hiding、restrictionやlocalityとも呼ばれる）：ローカル変数を導入し他のプロセスとのインタフェースを制限する

例えば、並行論理プログラミングは、並行制約プログラミングをエルブラン領域(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種類の制約が使われる。

  • 連続制約(Continus Constraints)
算術方程式と不等式で表されるような制約
  • 非算術制約(Non-arithmetic Constraints)
連続的には値が変わらない変数についての制約
  • 論理制約
論理式で表現される制約

ハイブリッド並行制約プログラミングは連続的な時間変化を扱うアニメーションツールなどへの応用が考えられている。

線形並行制約プログラミング

線形並行制約プログラミング（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）からなる。

  • 単純化規則（Simplification rule）
H1, ..., Hi ⇔ G1, ..., Gj|B1, ..., Bk .
  • 伝播規則（Propagation rule）
H1, ..., Hi ⇒ G1, ..., Gj|B1, ..., Bk .

単純化規則は、複数の制約を論理的に等価なより単純な制約に変換する。(例えば、X≦Y, Y≦X ⇔ X=Y.)

伝播規則は、論理的には冗長だが単純化に結び付くような制約を新しく追加する。(例えば、X≦Y, Y≦Z ⇒ X≦Z.)

LMNtal

LMNtal（Linked Multisets of Nodes transformation language、エレメンタル）はGHCの設計者である上田らによって開発された多重集合の書換えに基づく分散処理向け制約処理の言語モデルで、計算を階層的なグラフ構造の書き換えであるとした点に特徴がある[12]。 プロセスやルールは膜によってグループ化され、計算の局所化とグラフの階層化に利用される。循環構造や密に結合したデータ構造を容易に扱うことができ、またチャネルモビリティとプロセスモビリティの両方を備えている。JavaやC言語による言語処理系が開発されている。

プログラミング言語

並行制約プログラミングの考え方を取り入れたプログラミング言語の例を以下に示す。

並行論理プログラミング言語

Relational Language、Concurrent Prolog、Guarded Horn Clauses (GHC)とGHCの拡張であるKL1、PARLOG、Strandなどの並行論理プログラミング言語は、並行制約プログラミング言語の一種としてとらえることができる。 多くの言語はホーン節にガードを導入した形式でプログラムを記述するが、それらのガード部は制約の観測を行うask部と制約の追加を行うtell部の組み合わせとして一般化できる。

Janus

Janusは、GHCなどの並行論理プログラミング言語の影響を受けてSaraswatが開発した分散処理向け制約プログラミング言語で、多重集合と配列の書換えに基づく制約処理モデルを持つ[13]。Janusの多重集合と配列とは循環を含んでよく、多重集合は無限の「超多重集合」を表現でき、配列は論理プログラミング言語での項（term）を拡張した、有限幅の無限木を表現できる。さらに、ローマ神話のヤーヌスの二つの顔のように、実行時に現れる同じ変数は2回(入力側と出力側)以下という構文的な制限があり、実行時に失敗することがない特性を持っている。Janusは並行論理プログラミング言語と同じく、ストリームに基づいたデータフロー型のプログラムを素直にプログラムできる。

また、Janusの機能を制限したLucyと呼ばれる言語でアクターモデルが自然に表現できるため、KahnとSaraswatはアクターモデルが並行制約プログラミングの特別なケースだと主張した[14] 。

AKL

AKL (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プログラミングシステムがある。

脚注

  1. ↑ Jaffar, J., and Maher, M.J., Constraint Logic Programming: A Survey
  2. ↑ van Emden, M. H., and de Lucena, G. J. Predicate logic as a language for parallel programming
  3. ↑ Shapiro, E. A subset of Concurrent Prolog and its interpreter
  4. ↑ Ueda, K. Guarded Horn Clauses
  5. ↑ Michael Maher. Logic semantics for a class of committed-choice programs
  6. ↑ 6.0 6.1 Saraswat, V. A. Concurrent constraint programming languages
  7. ↑ Saraswat, V. A., Rinard M. and P. Panangaden. Semantic Foundation of Concurrent Constraint Programming
  8. ↑ Saraswat, V. A., A brief introduction to linear concurrent constraint programming
  9. ↑ Fagesa　F., Ruetb P. and Soliman S., Linear Concurrent Constraint Programming: Operational and Phase Semantics
  10. ↑ Frühwirth T., Introducing Simplification Rules. Internal Report ECRC-LP-63, ECRC Munich, Germany, October 1991, Presented at the Workshop Logisches Programmieren, Goosen/Berlin, Germany, October 1991 and the Workshop on Rewriting and Constraints, Dagstuhl, Germany, October 1991.
  11. ↑ Frühwirth T., Theory and Practice of Constraint Handling Rules. Special Issue on Constraint Logic Programming (P. Stuckey and K. Marriott, Eds.), Journal of Logic Programming, Vol 37(1-3), October 1998.
  12. ↑ 上田 和紀,加藤 紀夫, 言語モデルLMNtal
  13. ↑ Saraswat V., Kahn K., and Levy J. Programming in Janus
  14. ↑ Kahn K., and Saraswat V., Actors as a Special Case of Concurrent Constraint Programming
  15. ↑ Janson S. and Haridi S.,Programming Paradigms of the Andorra Kernel Language Logic Programming: Proceedings of the 1991 International Symposium 1991.
  16. ↑ Smolka　G., The Oz programming model

参考文献

  • Fagesa　F., Ruetb P. and Soliman S., Linear Concurrent Constraint Programming: Operational and Phase Semantics. Proc. 13th Annual IEEE Symposium on Logic in Computer Science," Indianapolis, 1998.
  • Gupta V., Jagadeesan R., Saraswat V. A., Bobrow D. G.: Programming in Hybrid Constraint Languages. Hybrid Systems II, LNCS 999, Springer-Verlag, 1995.
  • Jaffar, J., Lassez, J-L. and Maher, M.J., A Logic Programming Language Scheme. In Logic Programming Relations Functions and Equations. D. DeGroot and G.Lindstrom (Eds) Prentice-Hall, 441-467, 1986
  • Jaffar, J., and Maher, M.J., Constraint Logic Programming: A Survey. in Journal of Logic Programming, Volume 19/20, pp.503-581, 1994,
  • Michael Maher. Logic semantics for a class of committed-choice programs. In 4th international Conference on Logic Programming. MIT Press, 1987.
  • Kahn K., and Saraswat V., Actors as a Special Case of Concurrent Constraint Programming, Xerox Technical Report, 1990.
  • Saraswat V., Kahn K., and Levy J. Programming in Janus. Technical report, Xerox PARC, 1989.
  • Saraswat, V. A. Concurrent constraint programming languages. Ph.D. thesis, Dept. of Computer Science, Carnegie-Mellon University. 1989.*Saraswat, V. A., and Rinard M. Concurrent Constraint Programming. In Proceedings of Seventeenth ACM Symposium on Principles of Programming Languages, January 1990
  • Saraswat, V. A., Rinard M. and P. Panangaden. Semantic Foundation of Concurrent Constraint Programming. In Proceedings of 18th ACM Symposium on Principles of Programming Languages, 1991
  • Saraswat, V. A., A brief introduction to linear concurrent constraint programming. Xerox Palo Alto Research Center, 1993
  • 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.
  • Smolka　G., The Oz programming model. Computer Science Today, J. van Leeuwen(ed.),LNCS 1000, Springer-Verlag. 1995.
  • 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)
  • van Emden, M. H., and de Lucena, G. J. Predicate logic as a language for parallel programming. In Logic Programming, K. L. Clark and S. A. Tarnlund, Eds. Academic Press, London. 1982.
  • Mozart Consortium. The Mozart programming system, 1999.
  • 上田 和紀, 論理・制約プログラミングと並行計算. コンピュータソフトウェア Vol.25, No.3 pp.49-54, 2008
  • 上田 和紀,加藤 紀夫, 言語モデルLMNtal.(pdf) コンピュータソフトウェア Vol.21, No.2 pp.44-60, 2004

関連項目



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=並行制約プログラミング&oldid=111341」から取得