Prologのカットオペレーターの動作

2019年5月28日 2019年5月28日 12分40秒

ももうさ

スポンサードリンク

更新：2019/05/31　カットオペレーターの動作の部分を修正

こんにちは、ももやまです！
今日もPrologの記事です。

今回はPrologで使われるカットオペレーター ! についてわかりやすくまとめてみました。
カットオペレーターの動きについて例題などを使ってわかりやすく説明しています。

また、最後に動きが理解できているかの確認チェック問題も用意しています。

１．カットオペレーターとは
２．カットオペレーターの動作
- 例題
- 解説
３．練習
- 問題
４．さいごに

スポンサードリンク

１．カットオペレーターとは

皆さんは、Prologでこのようなプログラムを書いたことはありますか？

% delete(X,Y,Z) → リストXから要素Yをすべて除いたものがリストZ
delete([],_,[]). % リストXが空ならリストZも空、要素Yは関係ないので "_"
delete([Y|X],Y,Z) :- delete(X,Y,Z). % 要素Xと一致なら削除対象、リストZには追加しない
delete([A|X],Y,[A|Z]) :- delete(X,Y,Z),A \= Y. % 一致しなければ削除対象ではない。

このプログラムの下２行を他のプログラミング言語で書くとこのような感じになります。

if AとBが一致
# リストXに要素Yを追加するがリストZには要素を追加しない
end
if AとBが不一致
# リストXとリストZともに要素Yを追加
end

このように、他のプログラミングに相当する if 文みたいなものはあります。（今回だと A \= Y ）
ですがいちいち条件を書くのは少しめんどくさいです。

if AとBが一致
# リストXに要素Yを追加するがリストZには要素を追加しない
else
# リストXとリストZともに要素Yを追加
end

普通のプログラムなら上のようにわざわざ2回if文を使わずにelseを使いたくなりますよね。
Prologにもelse に相当するものがあればいいなと思ったことはありませんでしたか？

そこで登場するのがカットオペレーター !です！
カットオペレーターを使うと、else に相当する動作を実現することができます。
例えば、上のプログラムは以下のように表現できます。

% delete(X,Y,Z) → リストAから要素Bをすべて除いたものがリストC
delete([],_,[]).
delete([Y|X],Y,Z) :- delete(X,Y,Z),!. % 一致なら削除
delete([A|X],Y,[A|Z]) :- delete(X,Y,Z). % それ以外（一致じゃないなら）削除しない

このように条件をすっきりできますね！

カットオペレーター ! の左側にある関数が真になった場合、左側にある関数から成り立つ条件をすべて調べ、調べ終わったその時点で実行がすべてストップします。
下の方で、実際にカットオペレーターの動きを追っていきましょう！

スポンサードリンク

２．カットオペレーターの動作

カットオペレーターにはつぎのような効果があります。
次の2つのプログラムを例にして説明をします。

1つ目

Ans(A,B)  :- X(A),!,Y(B). % (1)
Ans(A,B)  :- Z(B).        % (2)

2つ目

Ans(A,B)  :- !,Y(B). % (1) 
Ans(A,B)  :- Z(B).        % (2)

1つ目のように!の左側にある条件 X(A)が1つでも真になった場合、そこでバックトラックが打ち止め。
例えば(1)にある ! の左側のプログラムX(A) が1つでも真になったとします。
すると、その時点で実行が終わります。（別のプログラム X(A) にはバックトラックしません）

しかし、2つ目のように! の左側になにもプログラムがない場合は、前提となる関数が存在しないので、その行にあてはまる関数がすべて真になります。1つ以上真になった場合そこで実行が止まります。

言い換えると、最初に真になるプログラムX を固定した上で、当てはまるすべてのプログラム Y が関数の解となり、それより下の行はすべて無視されます。

では実際に1つ例題でカットオペレーターの動きを確かめてみましょう。

例題

以下のPrologプログラムにおいて、p0(X,Y), p1(X,Y), p2(X,Y), p3(X,Y), p4(X,Y), p5(X,Y) を実行し、バックトラックさせながら解を求めると、それぞれ全部で何個の解が得られるかを答えなさい。

fly(hnd,mmb).  fly(hnd,fuk).  fly(hnd,hij).
fly(hnd,kix).  fly(fuk,kmi).  fly(fuk,oka).
fly(kix,fuk).
intl(hnd).  intl(nrt).  intl(kix).
intl(fuk).  intl(oka).
conv(hnd).  conv(fuk).  conv(oka).
p0(X,Y) :- fly(X,Y),intl(Y).
p0(X,Y) :- conv(Y).
p1(X,Y) :- !,fly(X,Y),intl(Y).
p1(X,Y) :- conv(Y).
p2(X,Y) :- fly(X,Y),!,intl(Y).
p2(X,Y) :- conv(Y).
p3(X,Y) :- fly(X,Y),intl(Y),!.
p3(X,Y) :- conv(Y).
p4(X,Y) :- fly(X,Y),intl(Y).
p4(X,Y) :- !,conv(Y).
p5(X,Y) :- fly(X,Y),intl(Y).
p5(X,Y) :- conv(Y),!.

解説

p0(X,Y)

まずはカットオペレーターのない場合。
これは地道に数えるだけの単純作業だ。
コンマでつながれた条件（今回だと fly(X,Y),intl(Y).）は、and条件を表す。 *1
なので、fly(X,Y) と intl(Y) の両方を満たさないと1個とカウントしてはいけない。

X = hnd, Y = fuk ? ;
X = hnd, Y = kix ? ;
X = fuk, Y = oka ? ;
X = kix, Y = fuk ? ;
% ここまでが fly(X,Y),intl(Y). の部分。全部で4個。
Y = hnd ? ;
Y = fuk ? ;
Y = oka ? ;
% conv(Y) の部分は全部で3個。

となり、合計7個となる。

p1(X,Y)

X = hnd, Y = fuk ? ;
X = hnd, Y = kix ? ;
X = fuk, Y = oka ? ;
X = kix, Y = fuk ? ;
%  fly(X,Y),intl(Y). は全部で4個。
% !の左側にプログラムがないため、!が含まれている文が1つでも真の場合、下のプログラムは実行されない。

!の左側にプログラムがない場合、!が含まれている文が1つでも真になった場合は下のプログラムは実行されないので conv(Y) は1つも実行されません。
よって、合計4個となる。

p2(X,Y)

p2(X,Y) :- fly(X,Y),!,intl(Y). % fly(X,Y) が1つでも真ならそこでプログラム終わり

今回は 'fly(hnd,mmb)' が真になったのでそこでもうほかのプログラムは実行されません。
さらに、p2(hnd,mmb) :- fly(hnd,mmb),!,intl(mmb). を満たすための intl(mmb) が存在しないため、解は1つもありません。
よって答えは0個。

p3(X,Y)

p2(X,Y) :- fly(X,Y),intl(Y),!. % fly(X,Y),intl(Y) が1つでも真ならそこでプログラム終わり
X = hnd, Y = fuk ? ; % fly(hnd,fuk),intl(fuk) があったのでここで実行終わり

今回は 'fly(hnd,fuk),intl(fuk)' が真になったのでそこでもうほかのプログラムは実行されません。
よって答えは1個。

p4(X,Y)

X = hnd, Y = fuk ? ;
X = hnd, Y = kix ? ;
X = fuk, Y = oka ? ;
X = kix, Y = fuk ? ;
%  fly(X,Y),intl(Y). は全部で4個。ここには!がないため通常通り。
Y = hnd ? ;
Y = fuk ? ;
Y = oka ? ;
% !の左側にプログラムがない場合、!が含まれている文が1つでも真の場合、下のプログラムは実行されない。下にはプログラムがないため、意味がない。

!の左側にプログラムがない場合、!が含まれている文が1つでも真になった場合は下のプログラムは実行されないのですが、下にプログラムなんてありませんね。
よって、このカットオペレーターは何も意味がないダミーでした。
合計7個が答え。

p5(X,Y)

X = hnd, Y = fuk ? ;
X = hnd, Y = kix ? ;
X = fuk, Y = oka ? ;
X = kix, Y = fuk ? ;
%  fly(X,Y),intl(Y). は全部で4個。ここには!がないため通常通り。
Y = hnd ? ; % conv(Y) が1つ真になったのでここで終わり

! の前に conv(Y) があるため、conv(Y) が1つでも真になったら実行打ち止めです。
今回は conv(hnd) が真になったときに打ち止めされます。答えは5個。

順番に答えは

p0(X,Y).  7個
p1(X,Y).  4個
p2(X,Y).  0個
p3(X,Y).  1個
p4(X,Y).  7個
p5(X,Y).  5個

です。

スポンサードリンク

３．練習

最後にカットオペレーターの動作を理解できてるかの確認テストを作ってみました。

問題

friend(mmy,gte).  friend(mmy,ntm).  friend(mmy,tro).
friend(hrk,mst).  friend(sen,gte).  friend(gte,mzk).
meet(gte,mmy).  meet(gte,sen).  meet(mzk,mky).
p0(X,Y) :- friend(X,Y),friend(Y,Z).
p0(X,Y) :- friend(X,Y),meet(Y,Z).
p1(X,Y) :- !,friend(X,Y),friend(Y,Z).
p1(X,Y) :- friend(X,Y),meet(Y,Z).
p2(X,Y) :- friend(X,Y),!,friend(Y,Z).
p2(X,Y) :- friend(X,Y),meet(Y,Z).
p3(X,Y) :- friend(X,Y),friend(Y,Z),!.
p3(X,Y) :- friend(X,Y),meet(Y,Z).
p4(X,Y) :- friend(X,Y),friend(Y,Z).
p4(X,Y) :- !,friend(X,Y),meet(Y,Z).
p5(X,Y) :- friend(X,Y),friend(Y,Z).
p5(X,Y) :- friend(X,Y),!,meet(Y,Z).
p6(X,Y) :- friend(X,Y),friend(Y,Z).
p6(X,Y) :- friend(X,Y),meet(Y,Z),!.