並行制約プログラミング
プログラミング・パラダイム |
---|
歴史
[編集]概要
[編集]h :- ask : tell | Bここでhは原子論理式、Bは原子論理式の集まりでプロセスの並列合成を表す。ask、tellはそれぞれ制約の観測と追加の集まりである。
特徴
[編集]応用
[編集]並行制約プログラミングのプロセス計算(process calculi)を応用したものとして、時間並行制約プログラミング、ハイブリッド並行制約プログラミング、線形並行制約プログラミングなどがある。また、並行制約プログラミングの様々な要素を並行プログラミングではなく制約充足系(constraint solver)の記述に用いたものとしてConstraint Handling Rules(CHR)がある。
時間並行制約プログラミング
[編集]時間並行制約プログラミング(Timed Concurrent Constraint Programming)は、並行制約プログラミングを制約の離散的な変化に応用したものである。プロセス計算(process calculi)上では、並行制約プログラミングに否定情報を扱うための機能を追加したデフォルト並行制約プログラミングに、プロセスを単位時間後に起動するオペレータ("Unit Delay")を追加したものと見なすことができる。
ハイブリッド並行制約プログラミング
[編集]線形並行制約プログラミング
[編集]線形並行制約プログラミング(Linear Concurrent Constraint Programming)は並行制約プログラミングを線形論理(Linear Logic)と呼ばれる論理体系に応用したものである。Vijay Saraswatにより1993年頃に可能性が指摘され[8]、 Francois Fagesらにより理論的にまとめられた[9]。
Constraint Handling Rules
[編集]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言語による言語処理系が開発されている。
プログラミング言語
[編集]並行制約プログラミングの考え方を取り入れたプログラミング言語の例を以下に示す。
並行論理プログラミング言語
[編集]Janus
[編集]AKL
[編集]Oz(Mozart)
[編集]脚注
[編集]- ^ Jaffar, J., and Maher, M.J., Constraint Logic Programming: A Survey
- ^ van Emden, M. H., and de Lucena, G. J. Predicate logic as a language for parallel programming
- ^ Shapiro, E. A subset of Concurrent Prolog and its interpreter
- ^ Ueda, K. Guarded Horn Clauses
- ^ Michael Maher. Logic semantics for a class of committed-choice programs
- ^ a b Saraswat, V. A. Concurrent constraint programming languages
- ^ Saraswat, V. A., Rinard M. and P. Panangaden. Semantic Foundation of Concurrent Constraint Programming
- ^ Saraswat, V. A., A brief introduction to linear concurrent constraint programming
- ^ Fagesa F., Ruetb P. and Soliman S., Linear Concurrent Constraint Programming: Operational and Phase Semantics
- ^ 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.
- ^ 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.
- ^ 上田 和紀,加藤 紀夫, 言語モデルLMNtal
- ^ Saraswat V., Kahn K., and Levy J. Programming in Janus
- ^ Kahn K., and Saraswat V., Actors as a Special Case of Concurrent Constraint Programming
- ^ Janson S. and Haridi S.,Programming Paradigms of the Andorra Kernel Language Logic Programming: Proceedings of the 1991 International Symposium 1991.
- ^ 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