ももの知恵の樹

論理型プログラミング

論理型プログラミングについて

論理型プログラミングとは

論理型プログラミングとは、事実と推論規則を用いた数理論理学の概念で記述するプログラミングパラダイムです。
この言語は「推論＝計算」という考えで設計されており、プログラムは「事実または推論規則」として記述し、どのように推論するかの手順は記述しないという特徴があります。
代表的なプログラミング言語として「Prolog」があります。


論理型プログラミングと命令型プログラミングとの違い

命令型プログラミングは、如何にして問題を解くか（How）についての手続き的な指示書となります。
これに対し、論理型プログラミングは、問題が如何なるものであるか（What）についての定義していく宣言的な明細書です。
命令型プログラミング（How）と宣言型プログラミング（What）の関係性に似ています。


論理型プログラミング言語「Prolog」

Prolog（プロログ）とは

Prologは、1972年にフランスのコンピュータ科学者 アラン・カルメラウアー氏によって開発されたプログラミング言語です。
この名称は、フランス語の「programmation en logique（論理によるプログラミング）」に由来します。
Prolog 言語の実装はいくつか存在しますが、最も有名なのが「SWI-Prolog」です。


Prologプログラムの構成について

Prologのプログラムは次の３つの要素から構成されます。

  1. 事実: 事物とその関係についての事実を宣言すること。
  2. 規則: 事物とその関係についての規則を定義すること。
  3. 質問: 事物とその関係について質問すること。

例えば、祖父-孫 関係の定義についてプログラミングすると以下の通りです。

【１:事実】「Bobのお父さんはCharlie」「Charlieのお父さんはDave」という事実を述語としてプログラミングします。 


father(Bob, Charlie).
father(Charlie, Dave).

【２:規則】「お父さんのお父さんはおじいちゃん」という規則を述語としてプログラムに追加します。 


grandfather(GC, GF) :- father(GC, F), father(F, GF).

【３:質問】Bobの祖父が誰かを質問します。 


?- grandfather(Bob, X).
X = Dave
Yes

PrologとSQLは似ている。

Prologとデータベース問い合わせ言語であるSQLは、動作原理的に非常に似ています。
両言語とも、データベースの中からクエリに対する解答を探し出すアルゴリズム（自動探索）が実行メカニズムとなっています。
プログラムには、データベース内のデータに対する具体的なアクセス方法ではなく、必要なデータが満たすべき性質や制約のみを記述します。


論理型プログラミングの概念

単一化（unification）

ユニフィケーションとは、命題を証明するために、既存の事実や規則を組み合わせる操作のことです。
簡単にいえば、パターンマッチング機能であり、推論規則と質問のパターンを比較することで、二つの項が同一になるような変数の代入を見つけ適用することです。
変数の値を何かと同一視することで、項同士が等しくなるようにする操作を単一化するといいます。


バックトラッキング

バックトラッキングとは、経路探索アルゴリズムのことで、Prologの自動検索機能を実現しています。
ユニフィケーションに失敗すると、別の解を見つけるために後戻り（最初に戻り）して、別の規則と比較します。


推論規則とは

推論規則とは、論理式から他の論理式を導く推論の規則です。
Prologでは、事実から事実を導くという動作を行います。


「一階述語論理式のうちホーン節と呼ばれる論理式」とは？

ホーン節（ホーンせつ、英: Horn clause）とは、数理論理学者のアルフレッド・ホーンによって提唱された、節（リテラルの選言結合命題）のうち、肯定形のリテラルの数が1つ以下の物をいいます。
Prolog のプログラムは節(ホーン節)を単位として記述します。
つまり、節が他のプログラミング言語における文に相当します。

節は述語と呼ばれる基本論理式から構成されます。
節には、ある述語が無条件で真であることを示す事実節と、ある述語が真となる条件として他のいくつかの述語が 真でなければならないことを示す規則節(規則)があります。


関連ページ