【LPN】10 Cuts and Negation

* 10 Cuts and Negation
** 1 The Cut
 - ! : predicate called cut.
 - cutは常に成功する。副作用する。副作用が大事。
 - fat-freeじゃなくてcut-free。
 - commit A to do,doing : Aに...することを義務づけ
   る。
 - cutを踏んだ時点で2つのことが義務となる。1つめは、
   現在のproof searchにおいて、そのclauseのみを探
   索の対象とすること(他のclauseは除外するというこ
   と)。次に、cutを踏む前にunify済みの変数について
   は、これ以降unificationは実施しないこと。
** 2 Using Cut
 - green cuts : cutsを入れても入れなくてもプログラ
   ムの意味(入出力の対応)に変化はないもの。green
   cutsに意味があるのは、効率があがるときである。
 - red cuts : cutsの有り無しでプログラムの意味が変
   わるcuts。
 - red cutsがある、ということはそのプログラムがあ
   まり宣言的ではない証左。なるほど。
** 3 Negation as Failure
 - fail/0 : バックトラックを強制する述語。
 - cut-fail combination : failによるバックトラック
   を抑制するイディオム。このイディオムがくると、
   そこでproof search自体がfailする(バックトラック
   しない)。
 - この章に入って、Prologの手続き的側面がどんどん
   導入されていく。。
 - negation : Monadic Boolean operations whose
   result have the Boolean value opposite to that
   of the operand.
 - cut-failじゃなくてnegation as failureを使うほう
   が安全。

neg(Goal) :- Goal,!,fail.
neg(Goal).

 - \+ : built-in negation as failure predicate.

 - cutsとnegation as failureの使い方についての完全
   なルールは存在しないケースバイケースの判断が必
   要。

 - まあ、プログラミングは、科学であるのと同じくら
   い芸術(技芸)でもあるので、自身が選択した言語と
   問題領域について理解を常に深めなければならない。
   だから面白いんだよ、プログラミングは。など。
** 4 Exercises
 - Exercise 10.1.
   p(X).
   X = 1.
   X = 2.

   p(X),p(Y).
   X = 1, Y = 1.
   X = 1, Y = 2.

   これ、間違えた。正解は、


?- p(X),p(Y).
X = 1,
Y = 1 ;
X = 1,
Y = 2 ;
X = 2,
Y = 1 ;
X = 2,
Y = 2.

?- 

   ということ。p(Y)でのcutはp(X)の探索には影響を及
   ぼさないことに注意。
   
   p(X),!,p(Y).
   X = 1, Y = 1.
   X = 1, Y = 2.
   
 - Exercise 10.2.

class(Number,positive) :- Number > 0.
class(0,zero).
class(Number,negative) :- Number < 0.

   これは数字のクラスに関する述語。正か負かゼロか
   でクラス分けしている。

   green cutsによる効率化。

class(Number,positive) :- Number > 0,!.
class(0,zero) :- !.
class(Number,negative) :- Number < 0.
   
 - Exercise 10.3.

   まず、cut-free。
   
split([],[],[]).
split([LH|LT],[LH|PT],N) :-
        LH >= 0, split(LT,PT,N).
split([LH|LT],P,[LH|NT]) :-
        LH < 0, split(LT,P,NT).

   続いてgreen cuts。

split([],[],[]) :- !.
split([LH|LT],[LH|PT],N) :-
        LH >= 0, !, split(LT,PT,N).
split([LH|LT],P,[LH|NT]) :-
        LH < 0, !, split(LT,P,NT).

 - Exercise 10.4.

   うーん。むずかしい。cutは宣言的かつ手続き的なの
   で、慣れれば強力かもしれないが、慣れないと中途
   半端で考えにくい。特にunificationがどう効いてく
   るかが問題になると、自分で束縛管理した方が楽じゃ
   んと思えてしまう。
   
   ここは後日、再チャレンジ。



** 5 Practical Session   
 - 1.

   \+ version.

nu(A,B) :- \+ A = B.

   \+ cut-free version

nu(A,B) :-
        A = B, fail;
        A \= B.

   cut-fail combination version

nu(A,B) :- A = B, !, fail.
nu(_,_).
   
 - 2.

  頭がまわらないので、これも後日。

よろよろ。