Prologで論理的にプログラミングを学んでいます（再帰または帰納）

　AI言語Prologによるプログラミング学習の第4回です。テキストは、「地味に論理的」です。
　内容は、Prologにおける再帰についてです。

再帰とは

　これまでに二つの形式の論理式が登場した、事実と規則である。
　規則には、それ自身に関しての関係を定義するものがある。この自己言及は、再帰と呼ばれる。
　Prologでは、再帰は唯一の繰り返し構造である。
　再帰について考える最も簡単な方法は次のようなものである。
　"任意の大きな鎖は、その鎖のなかの一つの環（コマ）が次の環にどのように連結されているか記述されることにより、記述される"

　例えば、鉄道の例においては、「ある駅が他の駅に一つ以上の路線により接続されるならば、その駅は他の駅から到達可能（reachable）である」としてrechability関係の定義がなされる。

reachable (駅A, 駅B).

　二つ以内の間の駅を経由する経路が存在するとき、ある駅は他の駅から到達可能となる。そこで、以下の定義（再帰でない）を用いることも考えられる。

reachable (X, Y) :- connected (X, Y, L).
reachable (X, Y) :- connected (X, Z, L1), connected (Z, Y, L2).
reachable (X, Y) :- connected (X, Z1, L1), connected (Z1, Z2, L2), connected (Z2, Y, Z3).

再帰による定義

　この方法にて全てのreachability関係を定義しようとするならば、より多くの長い規則が必要となる。再帰は、このような任意の長さの鎖を定義できる簡便で自然な方法である。

reachable (X, Y) :- connected (X, Y, L).
reachable (X, Y) :- connected (X, Z, L), reachable (Z, Y).

　二つ目の規則は、「駅Zが路線Lにより駅Xに直接接続され、かつ駅Yが駅Zから到達可能であるならば、YはXから到達可能である」を表す。

バックトラック

　Prologにおける「問い合わせの回答」は検索の手続きであり、その回答は事前に為された選択に依存している。

　選択は、行き詰まりを招くかもしれない。例えば、reachability関係についての再帰的な式についての検討が、再帰的でない式よりも先に行われたとすると、行き詰まりが起こるかもしれない。このような場合には証明木を完成させることができない。

 　Prologは、この失敗から復帰せねばならず、それは、以前の選択を再び検討するために証明木を遡ることで為される。
　この検索の手続きは、バックトラッキングと呼ばれ、後に説明される。

---

まとめ

　今回は、読み終えてから記事を書くまでの間隔が空いたので、初読の感想を何も覚えていません。
　読み返しての感想は、具体例がたくさんあるなあ、です。
　もう少し再帰についての本質的な話があるのかと期待していたのですがありませんでした。
　再帰理論をやるには頁数がありませんし、そもそも読者の基礎論が定まっていないのでできないのでしょう。

　次回は、構造化された項（複合データ構造）について学ぶ予定です。記事を上げるもう少し周期を短くしたいです。