【LPN】3 Recursion

* 3 Recursion
** 1 Recursive Definitions
 - stork: コウノトリ
 - "Let's now consider both the declarative and
   procedual meanings of the definition" ！ 両方の
   意味があるのか！
 - 宣言的な意味は、PrologのKBの内容を論理的な言明
   群と考えたとおりの字句通りのこと。
 - 手続き的な意味は、そのKBに具体的なクエリをしたと
   きの、具体的にPrologが実施するproof search処理の
   こと。
 - descendant: 子孫、末裔
** 2 Rule Ordering, Goal Ordering, and Termination
 - Prologは、論理プログラミング言語として、完全で
   はない。ここで完全ではない、というのは、宣言的
   な記述をするだけであとは計算機がやってくれると
   いうことができないということ。
 - Prologでは、手続き的な側面も大事である。それは、
   KBを上から下に探索するということ、サブゴールを
   左から右に探索するということ、探索が失敗したと
   きに直前の選択ポイントにバックトラックするとい
   うこと。
 - goalsの順番は重要。探索が止まらなくなる。
 - left recursive rule: 左再帰ルール？
 - headのfunctorはbodyではできるだけ遠くへ置け。
 - 実践的に言うと、まず論理プログラミングの精神に
   て問題を宣言的に記述する。それが終わったら、
   Prologの手続き的観点からそれをチューンナップせ
   よ。
** 3 Exercise
 - Exercise 3.1.

descend(X,Y) :- child(X,Y).
descend(X,Y) :- descend(X,Z), descend(Z,Y).

   まず、これは宣言的には正しそうだ。しかし手続き
   的には止まらなくなりそうだ。止まらないケースを
   シミュレーションしてみる。

   descend(a,b).というクエリに対して、

   まず、

descend(X,Y) :- child(X,Y).

   に失敗するとする。すると、

descend(X,Y) :- descend(X,Z), descend(Z,Y).

   を適用するので、サブゴールは、

descend(a,_G1), descend(_G1,b).

   となる。左からやるのがルールなので、
   descend(a,_G1)を探すが、
 
descend(X,Y) :- child(X,Y).

   は失敗するとする。すると、

descend(a,_G2), descend(_G2,_G1).

   の探索になり、これは終了しない探索になる。

 - Exercise 3.2.

directlyIn(natasha,irina).
directlyIn(olga,natasha).
directlyIn(katarina,olga).
in(X,Y) :- directlyIn(X,Y).
in(X,Y) :- directlyIn(X,Z), in(Z,Y).

 - Exercise 3.3.

travelFromTo(X,Y) :- directTrain(X,Y).
travelFromTo(X,Y) :- directTrain(Y,X).

travelFromTo(X,Y) :- directTrain(X,Z),travelFromTo(Z,Y).

 - Exercise 3.4.

greater_than(succ(X),0).
greater_than(succ(X),succ(Y)) :- greater_than(X,Y).

 - Exercise 3.5.

swap(leaf(X),leaf(Y)) :- =(X, Y).
swap(tree(LL,LR),tree(RL,RR)) :-
        swap(LL,RR),
        swap(LR,RL).

 - Prologのfunctorを立案するときの頭の使い方はLisp
   系言語の関数立案時とは全然違う。
 - Lisp系のように再帰が便利とか重要とかいうレベルで
   はなく、再帰が無いとプログラムにならない。書けな
   い、じゃなくて、ならない。再帰はPrologの核であ
   る。ウーン。うまい表現がみあたらない。
** 4 Practical Session   
 - 論理プログラミングは探検的プログミング手法には
   向かないかもしれない。宣言的な記述を考えるのっ
   て、何か頓知に近い気がする。慣れの問題なのかなぁ。

PAIPに通じる概念や観点が散見される。やはり古典的AIというのはProlog的なのだろうか。

こつこつ。