事実から新しい事実を作る
Prolog の規則とは、「これらが成り立つなら、これも成り立つ」と書く文です。規則を使うと、書いていない事実を、書いた事実から導けます。
家系図に「親」の事実だけがあるとします。「祖父母」や「先祖」を1行ずつ書くのは大変です。規則を1つ書けば、Prolog が自分で祖父母や先祖を見つけます。
このレッスンのゴール
メモ
他の事実を使う規則と、自分を呼ぶ再帰の規則を書くことができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 規則 | 他の文が成り立つとき成り立つ文 | grandparent(X, Z) :- ... |
| 頭部 | 規則の :- より左の、導かれる文 | |
| 本体 | 規則の :- より右の、条件の並び | |
| 再帰 | 規則が自分自身を使うこと | |
| 基底 | 再帰を止める、最も単純な場合 |
学生が入力するセルは、このプレビューでは空白です。
規則は「もし〜なら」の文である
規則は、頭部 :- 本体. の形で書きます。:- は「もし」、本体の中のコンマは「かつ」と読みます。
たとえば祖父母は、「X が Y の親で、Y が Z の親なら、X は Z の祖父母だ」と書けます。Y は途中の人で、Prolog が自分で探します。
例: 祖父母の規則
% X は Y の親で、Y は Z の親なら、X は Z の祖父母です。
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).family.pl の規則を読む
docker exec prolog cat family.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
dan の祖父母を探す
docker exec prolog swipl -q -g "forall(grandparent(X, dan), writeln(X))" -t halt family.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
兄弟には「同じ人ではない」が要る
兄弟は、「同じ親 P を持ち、X と Y が別の人」です。family.pl の規則は sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y. です。\= は「等しくない」の意味です。
この条件がないと、ann の兄弟に ann 自身も入ります。どの子も、自分と同じ親を持つからです。
dan の兄弟を探す
docker exec prolog swipl -q -g "forall(sibling(dan, X), writeln(X))" -t halt family.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
自分自身は兄弟か
docker exec prolog swipl -q -g "(sibling(ann, ann) -> writeln(yes) ; writeln(no))" -t halt family.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
自分を使う規則で先祖をたどる
先祖は、何代さかのぼってもよい関係です。だから規則は2つに分けます。1つめは基底で、「親は先祖だ」です。2つめは再帰で、「親の先祖も先祖だ」です。
2つめの規則は、本体の中で ancestor 自身を使います。事実が尽きると、探索は自然に止まります。
例: 先祖の2つの規則
% 基底: 親は先祖です。
ancestor(X, Y) :- parent(X, Y).
% 再帰: Z が X の子で、Y が Z の子孫なら、X は Y の先祖です。
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).例: ancestor(tom, eve) を調べる
| 手順 | 試す規則 | 結果 |
|---|---|---|
| 1 | 基底 parent(tom, eve) | 事実にないので失敗 |
| 2 | 再帰 parent(tom, Z) | Z は ann |
| 3 | ancestor(ann, eve) を調べる | 基底も再帰も失敗。戻る |
| 4 | 再帰 parent(tom, Z) の次の答え | Z は ben |
| 5 | ancestor(ben, eve) の基底 parent(ben, eve) | 成功。全体が成功 |
学生が入力するセルは、このプレビューでは空白です。
eve の先祖をまとめて出す
docker exec prolog swipl -q -g "findall(P, ancestor(P, eve), L), writeln(L)" -t halt family.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
先祖と子孫の組は全部でいくつか
docker exec prolog swipl -q -g "aggregate_all(count, ancestor(_, _), N), writeln(N)" -t halt family.plここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
「再帰の規則を1つ書けば足りる」と考える人が多くいます。止める基底の規則がないと、先祖の先祖の先祖と、どこまでもたどってしまいます。再帰の規則には、必ず基底の規則を添えます。
Python で同じ形を書く
# 子から親を引く辞書です。
PARENT = {"ann": "tom", "ben": "tom", "cat": "ann", "dan": "ben", "eve": "ben"}
def is_ancestor(old, young):
if young not in PARENT:
return False # 基底: 親がいないので、たどれない
if PARENT[young] == old:
return True # 基底: 親が見つかった
return is_ancestor(old, PARENT[young]) # 再帰: 親の先祖を調べる
print("tom は eve の先祖ですか:", is_ancestor("tom", "eve"))
# "tom" を "ann" に変えて、もう一度実行してみましょう。