論理型言語(Prolog)入門

導入

最近、論理プログラミングの勉強を始めました。理解をより深めるために、自分の言葉でまとめたメモを投稿していこうと思います。

---

1. Prologとは

Prologとは、物事の関係性などの論理関係を主に扱うプログラミング言語である。C言語などの手続き型言語とは異なり、手続き的に制御構造を記述しない点が特徴である。

2. Prologの文法

以下のPrologプログラムを用いて、Prologの文法を説明する。

oyako.pl

parent(namihei, sazae).
parent(sazae, tara).
groundparent(X, Y) :- 
  parent(X, Z),
  parent(Z, Y).

oyako_qa.pl

?- parent(namihei, sazae).
yes
?- parent(tara, sazae).
no
?- parent(sazae, X).
X = tara
?- groundparent(namihei, tara).
yes

2-1. 項（定数、変数、構造）

項とはnamihei、X、parentなどの１つの文字列で表されるものである。項には定数、変数、構造が存在する。

定数

定数には数とアトムが存在する。数は0、1.1などの数値のことである。アトムは英小文字で始まる文字列のことである。namihei、sazaeなどが定数にあたる。

変数

変数とは英大文字または下線文字（「_」）から始まる文字列である。X、Y、Zなどが変数にあたる。

構造

構造とは1つ以上の定数、変数を持ったオブジェクトである。parent(namihei, sazae)などが構造にあたる。この時、「（）」の外にある文字列を関数子と呼ぶ。また、「（）」の中にある要素を引数と呼ぶ。

※引数の個数が異なれば、関数子に同じ名前を付けることができる。
parent(X,Y)とparent(X,Y,Z)は異なるものとして認識される。

2-2. 節（事実、ルール、質問）

Prologプログラムは節の組み合わせで記述される。節は句読点（「.」）で終了する1文のことである。節には、事実、ルール、質問の３つの型がある。

事実

事実とは必ずyesとなるものである。事実は定数を要素として持つ構造である。以下のようなものが事実である。

oyako_fact.pl

parent(namihei, sazae).
parent(sazae, tara).

ルール

ルールは与えられた条件によってnoもしくはyesとなるものである。以下のようなものがルールである。この時、「:－」より前を頭部、「:－」より後を本体と呼ぶ。本体と頭部はどちらも構造である。本体がyesであれば、頭部もyesとなる。

oyako_rule.pl

groundparent(X, Y) :- 
  parent(X, Z),
  parent(Z, Y).

質問

質問はプログラムの何がyesかを問うものである。質問は構造である。構造が定数のみの場合はyesまたはnoが出力される。構造に変数が含まれる場合は、変数に当てはまる定数が出力される。

oyako_qa.pl

?- parent(namihei, sazae).
yes
?- parent(tara, sazae).
no
?- parent(sazae, X).
X = tara
?- groundparent(namihei, tara).
yes

2-3. 算術式

算術式は「+、-、<」などのことであり、四則演算や項の比較などで用いられる。

単一化

単一化（「=」）とは左右の項を等しくすることである。例えば、「1 = 1」などはyesとなる。単一化は左右の項を等しくすることであり、四則演算は行わず文字列として保存される。そのため、「3 = 1+2」はnoとなる。

※四則演算を行いたい場合は「is」を用いる。「X is 1+2」は「X = 3」となる。

四則演算

加算は「+」、減算は「-」、乗算は「＊」、除算は「/」で行う。

項の比較

「==」は両辺が同一の項であればyesとなる。「\==」は両辺が同一の項でなければyesとなる。「@<」は項の大小比較であり、左辺より右辺の項の辞書順が前であればyesとなる。

3. Prologの実行

Prologの探索手順

Prologは以下のような手順で探索を行う

1. 目標リストを作成する
2. 目標リストが空であれば成功（終了）
3. 目標リストの先頭の要素を取り出す
4. プログラムの最初から目標にマッチするものを探す
5. マッチしたものがあればその節の本体を目標リストに追加する
6. マッチしなければバックトラックする
7. ２に戻る

Prologの探索例

groundparent(X,Y)の実行を行う

一周目

1. 目標リスト：groundparent(X,Y)
2. 目標リストが空でないので続ける
3. 先頭の目標：groundparent(X,Y)
4. groundparent(X, Y) :- parent(X, Z),parent(Z, Y).にマッチ
5. parent(X, Z),parent(Z, Y)を目標リストに追加

二周目
6. 目標リストが空でないので続ける
7. 先頭の目標：parent(X,Z)
8. parent(namihei, sazae).にマッチX=namihei,Z=sazae
9. 本体はないので目標リストには何も追加しない

三周目
10. 目標リストが空でないので続ける
11. 先頭の目標：parent(Z,Y)
12. parent(sazae, tara).にマッチZ=sazae,Y=tara
13. 本体はないので目標リストには何も追加しない

四周目
14. 目標リストが空であるので成功X=namihei,Y=tara

まとめ

• Prologとは論理関係を主に扱うプログラミング言語
• 項には定数、変数、構造が存在する
• 節には事実、ルール、質問が存在する

参考

以下のサイト・参考書が分かりやすく、参考にさせていただきました。
『Prologへの入門』(I.Bratko 著)
https://ja.wikipedia.org/wiki/%E8%AB%96%E7%90%86%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0