Prolog 概要

Prolog

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

概要

1972年ごろにフランスのアラン・カルメラウアーとフィリップ・ルーセルによって考案された[2]

成立の事情から、Prolog プログラムは論理式とみなされ、その実行は述語論理によって述語が定義された環境における定理証明に擬して解釈されることが多い。利用者は論理プログラミングの枠組みを、取り分け述語論理を学習することで、この枠組みに極めて忠実なこの言語の基礎的な構造のほとんどを理解できる。その言語仕様はこの枠組み以外には考案者たちも含めてそれ以上の拡張をほとんど行っていないため、他のプログラム言語とは異なり、学習しなくてはならない概念や用語もまた、述語論理のものだけでこと足りる。基本的に計算機科学の新しい概念や新しい手法とは無縁である。ただし、SWI-Prolog等の処理系では様々な機能拡張の試みが行われている。一階述語論理は型理論や操作的意味論の研究論文で多数用いられており、今後、再注目される可能性がある。

述語論理と論理プログラミング

Prologプログラム一階述語論理に基づいてデータ間の関係を示す命題として記述され、処理系がそれらに単一化(ユニフィケーション)と呼ばれるパターンマッチングを施しながら、与えられた命題が成立するか再帰的手続きによって探索している。

プログラムの実行は述語集合が定義された環境の元で、質問することによってなされるが、これは反駁という述語論理的な証明過程を模して、処理系が用意する導出木と呼ばれるグラフをたどって解を得る過程である。 Prolog のもととなるこの演繹手法は導出と呼ばれ、自動定理証明の研究において Prolog 開発以前からよく知られていた。Prolog は、導出において節を頭部が一つの命題からのみなるホーン節に限定したもので、この場合の導出をSLD導出(Selective Linear resolution for Definite clause)と呼ぶ。ホーン節に限定しているということは、つまり、Prolog は任意の述語をそのまま扱えるわけではない。Prolog が述語の形式をホーン節に限定した理由は、もし頭部に項の連言を認めるならば、導出時の計算量が爆発的に増大して、全ての解を得ることの保証が難しくなることが必至だからである。

述語論理を論理的な背景に持つことによって、Prolog のプログラムはその正しさを確認することが比較的容易である。同時に、プログラマは Prolog でプログラミングすることが何を意味するかを明確に理解した上で、プログラムを書いていくことができる。

非述語論理的な立場

上記は Prolog の一つの解釈である。一方、Prolog というプログラム言語を述語論理という枠にはめないで捉える立場もある。導出、単一化、非決定性、双方向性、関係データベースといったこの言語に独特の機能とその表現力、記述力に着目し、そのプログラム言語としての可能性を率直に評価しようとするものだ。

新たに Prolog を学びたいと思う人は、他のプログラム言語を全く知らなくても、ソフトウェア科学的な予備知識や概念に不通であっても、単一化という単純なルールをほとんど唯一の基軸として、パズル的な、あるいはゲーム的な感覚にだけ導かれて、プログラムを簡単に書き進むことができる。さらに、どの言語にも比して平坦で、平明な言語構造を持つ Prolog はラベル名(アトム、関数名、述語名)に適切な意味性を付与することにより、自然言語の領域にも接近したプログラミングが期待できるほとんど唯一の言語でもある。

十分述語論理的な教養を持った上で Prolog を学び、そのプログラムを書くならば、短期間で高度で安定したプログラムを書くことができる。しかし、それを前提としないでも、Prolog は冒険的で、未知の領域に満ちたプログラム言語なのである。

実はこれらの主張は、述語論理的な主張に隠れて、これまであまり強調されたことがなかった。

このような立場や主張が生まれる背景には、Prolog が期待されたほどにはソフトウェア革新の担い手になり得ていない理由が、その後の数理論理学の学問的な評価をもって、プログラム言語としての可能性を十分検証することを放棄して、定理証明といった狭い目的へ封じ込めようとする風潮を生んだことにある、という反省がある。そのことを踏まえて、Prolog が述語論理から成立したことにこだわらず、実在するプログラム言語として自由な視点からこの言語を見直そうとするものである。

記号処理用言語・人工知能言語

PrologLISP の資産の多くを継承して間違いなく記号処理用の言語であるが、人工知能言語として分類されることも多い。これは、人工知能の世界では述語論理が古くから理論的な柱の一つとなっているからである。述語論理を基礎とするトップ・ダウン式の問題解決と同じく述語論理を基礎とする Prolog の駆動機構の相性は当然良いため、人工知能研究に広く利用されてきた。特にエキスパートシステムで多用されるプロダクションシステムにおいては、ルールを自然に自ら動的に変更できる能力を持つことと、後ろ向き推論と呼ばれる推論が Prolog の導出過程そのものであることから、その最も主要な記述言語の位置を占めてきた。

宣言型言語

Prolog は一階の述語論理に対応することから論理型言語に分類される汎用言語であるが、その主張の一行一行を独立して論理式とほとんど等価な表現で行うことから、最も代表的な宣言型言語と見なされている。Prolog のプログラム単位である述語の各節の本体に現れる質問単位である副目標数は平均5個以内と極めて少ない。この副目標と各節の頭部に現れる引数の組み合わせによって得られる関係が述語の意味を構成している考えられる。これが宣言型とされるゆえんである。

<頭部> :- <本体>.  % Prologの節は頭部と本体によって構成される。

% 述語定義は複数の節からなる。本体は幾つかの副目標からなる。
% 副目標の全てが真となった時に節の宣言は成立する(節は真となる)。

述語名(引数_1,引数_2) :- <副目標_1>,<副目標_2>.
述語名(引数_1,引数_2) :- <副目標_3>
・・・

単一化

単一化は1960年代の述語論理理論の発展の鍵となった概念であるが、Prolog が述語論理に導かれて機械による自動証明を実現するためのプログラム言語として成立したことから、必然的にこの言語の必須の最も重要な機構となった。単一化は副目標(質問)と対応する定義節の頭部のパターンが完全に一致するか、調べることで、節の選択[注 1]を可能にする。さらに、Prolog の実行順序等の制御は単一化のからくりを利用してプログラミングされる。

簡単なからくりでかつ極めて強力な単一化であるが実行コストも大きい、すなわち実行速度が遅くなる原因となる。さらに、パターンとして認識することと引き換えに、引数での関数評価は不可能になった。独立して節の本体で式評価を記述しなくてはならないため、数値計算ではやや冗長になる。 これらの点は、単一化の強力さとのトレードオフの関係になっている。

動的型付け

型付けは動的型付けに分類できるが、言語仕様の中に型概念は登場しない。上記の単一化、バックトラッキング、と論理変数の束縛においては独特のものがあり、その実行は型推論の実行過程に酷似している。既に Prolog はその引数の引渡し時に単一化という厳密なパターンマッチングを施すことに多大なコストを掛けた。単一化だけでプログラムをコントロールできる言語が Prolog であるといっても過言ではない。この単一化のみによる簡素で強力なプログラムコントロールの足を引っ張ることに成り兼ねない、型付けの強化は、Prolog 言語とその支持者によって受け入れられることはないだろう。

非オブジェクト指向言語

Prolog は言語による思考をモデル化して主語・述語といった意味での文中の述語を特に重視して記述する系である。この一点からも、対象物を中心に記述していくオブジェクト指向とは距離が大きい。述語論理以前にオブジェクトありきとする立場を一般には取らない。

いくつかの処理系では、オブジェクト指向言語としての拡張が行なわれているが、オブジェクトを中心に設計されることは、論理プログラミングを重視して記述される限りほとんどない。分類するならば、非オブジェクト指向言語に分類される。オブジェクト指向に拡張された言語としては

  • Visual Prolog
  • Logtalk

が存在する。

オンメモリデータベース

後に述べるが Prolog の述語はその構造が頭部と本体と分かれていて、本体はルールを意味するため、全体として、ルールを持ったデータベース、演繹データベースとして捉えることができる。これはPrologプログラム全体がデータベースであるということだから、データベースの表現としては最強のクラスに属する。一方、事実を表す本体のない(強制的に真)頭部のみの定義節による述語は関係データベースとその集合論的な性質で一致する。収集した情報を一つの述語に対して多数の頭部のみを持った節の集まりとして定義することにより、オンメモリ関係データベースを構築することが可能である。しかし、Prologをデータベース管理システムとして捉えた場合、 assertretractsetofbagoffindall という組込述語を持つこと以外には、管理機構としての特別の組込述語が用意されている訳ではなく、ディクショナリ管理などのための述語定義をユーザが追加する必要がある。

非決定性と双方向性

関数型言語等、他のプログラミング言語と比較しての Prolog の特長は、上記、一階述語論理に基づくこと、単一化、データベース言語的性格の他に、非決定性双方向性が挙げられる。

非決定性は、解が唯一とは限らない場合、処理系側から見てひとつの解に決定できない場合、外部からの選択の余地を与える。そういうことが当然可能なこととして述語は定義されていく。インタプリタトップではなく、導出を繰り返すプログラム内部にあっては、処理系側とした所を述語と置き換えて考えると、非決定性の述語の解を決定するのは、前方または後方に連接する質問(副目標)である。前方の副目標群から引数経由で与えられる情報によって副目標は一つの解を作り出すが、この解が真であるとするのは最終的に後方に連接する副目標である。この後方に連接した副目標が全て真となった場合に限り副目標は真となる。後方に連接する副目標のどれかが真にならなかった場合は、それが存在すればであるが別解を用意しなくてはならない。ここでも非決定性の述語、ここでは副目標から見ての解の決定権は、外部にあるということになる。

非決定性は導出の過程、取り分けバックトラックアルゴリズムと一体化しており、Prolog プログラムの制御の根幹のひとつである。ただ、非決定性述語実行時に見られる論理変数の 束縛→解放→再束縛という遷移、すなわち一度束縛されたものが別のものに再度束縛されるということを好ましくないとする見方もある。

双方向性は、述語が実行された場合の返り値は真または偽だけであり、その代わりとして引数内の変数で値の授受を終始するのだが、このとき、入力として使われた変数が出力に、出力として使われていた変数が入力として使うことのできる述語となることがある。この性質を双方向性という。多くの場合、双方向性を持つ述語はそれ自体多義性を持つ。例えば append という3引数の述語は第一引数と第二引数に具体的なリストが来て呼ばれた時は、リストを結合する意味でよいが、第三引数がリストで第一引数と第二引数が変数の状態で呼ばれた場合その意味は、リストを分解する、がふさわしい。既に存在するリストを、それが結合されて存在したものと考え、それではどのように結合されていったか、あるいは、どのような組み合わせで結合されていったのかを、示していると解釈できる。

このような、双方向性は Prolog の述語自らがリバースエンジニアリング的開示能力を持ち、それを示していると捉えることができる。この性質は、Prologを含む論理型プログラム言語の持つ際立った特徴であり、プログラム作成時はもちろん、テスト、デバッグなどの検証の各段階でプログラムコードに対する見通しを向上させる。

Prolog プログラミングの難しさ

プログラマは引数の単一化、再帰/失敗駆動等のプログラムパターンの選択、非決定性、双方向性といった特長をできる限り生かすことなどに配慮しながら、述語の骨格を決めプログラミングを進める。しかし、これらの特長、性質は複合した場合には相当に複雑であり、制御上相反する部分も多々ある。Prolog では、述語論理を逸脱して計算量/資源量/制御の調整に当たる述語「!」(カット)を導入してこの問題に対処しているが、Prolog プログラミングの難しさはこの調整部分に集中している。


注釈

  1. ^ : resolution、融合
  2. ^ : David H.D.Warren
  3. ^ W. F. Clocksin
  4. ^ : C. S. Mellish
  5. ^ : extended self-contained Prolog
  6. ^ : Bruce A. Tate
  7. ^ : Daniel Jackson
  8. ^ : Ivan Bratko

出典

  1. ^ Alain Colmerauer, Philippe Roussel. The birth of Prolog, p.2.
  2. ^ a b Robert Kowalski. The Early Years of Logic Programming, p.38.
  3. ^ Buss, Samuel R., "On Herbrand's Theorem".
  4. ^ Alain Colmerauer and Philippe Roussel, The birth of Prolog, p.6.
  5. ^ Alain Colmerauer and Philippe Roussel, The birth of Prolog, pp.14-15.
  6. ^ 古川 康一, p.5.
  7. ^ 古川 康一, p.5.
  8. ^ 萩野達也,桜川貴司,柴山悦哉
  9. ^ https://www.complang.tuwien.ac.at/ulrich/iso-prolog/SWI7_and_ISO
  10. ^ K-Prolog について”. 2020年1月10日時点のオリジナルよりアーカイブ。2021年9月11日閲覧。
  11. ^ https://www.researchgate.net/publication/277325585_Aspects_of_Prolog_history_Logic_Programming_and_Professional_Dynamics






固有名詞の分類


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

辞書ショートカット

すべての辞書の索引

「Prolog」の関連用語

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

   

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



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

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

©2021 GRAS Group, Inc.RSS