第13回 Prolog の総合演習

今日の課題

■ 非決定性プログラミング

「非決定性」とは、ある状態のシステムに、ある入力をしたときに、得られる出力とシステムの状態が１通りにはならないことを言う。たとえば、「第11回Prologの概要」で作ったプログラムで、「?- like(goro,X).」の質問をすると、X に該当する名前は１つではなく、幾つも存在した。

非決定性プログラミングでは、複数の選択肢から正しいものを1つ選んだものとして、プログラムを書く。たとえば、小レポートで作成したが、「goro が好きであり、かつ、rokuro も好きである人は誰か」という質問では、「?- like(goro,X), like(rokuro,X).」と記述した。「like(goro,X)」の結果、Xは複数の答えが存在するが、Xに適切なものが選択されたとして、「like(rokuro,X)」が実行される。

■ バックトラック

非決定性プログラミングを実行するには、2通りの方法がある。

Prolog では、バックトラックの機能が備わっているので、非決定性プログラムが簡単に作れる。

バックトラックとは、選択の必要が生じると、その地点を覚えておき、どれか1つを選択し、処理を進める。結果に不都合があると、覚えておいた地点に戻り、別を選択して処理を進めるというものである。

□ トレース(trace)

バックトラックの生じる様子を Prolog の実行中に観測することができる。トレースという機能である。

例1

以下のプログラムにおいて、「?- like(hanako,X).」に非決定性のあることを確認しよう。そして、「?- like(hanako,X), like(hiroko,X).」で適切に選択されて答えが得られることを確認しよう。さらに、トレースを使って、様子を見てみよう。 

%-*-prolog-*-
% list1301.pl
like(hanako,apple).
like(hanako,orange).
like(hanako,lemon).
like(hanako,grape).

like(hiroko,orange).
like(hiroko,melon).
like(hiroko,lemon).

like(hikari,apple).
like(hikari,lemon).

トレースを使う様子を以下に示す。自分で操作してみよう。 

[tokuhisa@dee Prolog]$ pl
?- ['list1301.pl'].
% list1301.pl compiled 0.00 sec, 1,276 bytes
true.

?- trace.
Unknown message: query(yes)
[trace]  ?- like(hanako,X), like(hiroko,X).
   Call: (8) like(hanako, _G313) ? creep
   Exit: (8) like(hanako, apple) ? creep
   Call: (8) like(hiroko, apple) ? creep
   Fail: (8) like(hiroko, apple) ? creep
   Redo: (8) like(hanako, _G313) ? creep
   Exit: (8) like(hanako, orange) ? creep
   Call: (8) like(hiroko, orange) ? creep
   Exit: (8) like(hiroko, orange) ? creep
X = orange ;
   Redo: (8) like(hiroko, orange) ? creep
   Fail: (8) like(hiroko, orange) ? creep
   Redo: (8) like(hanako, _G313) ? creep
   Exit: (8) like(hanako, lemon) ? creep
   Call: (8) like(hiroko, lemon) ? creep
   Exit: (8) like(hiroko, lemon) ? creep
X = lemon .

[debug]  ?- abort.
% Execution Aborted
?-

「Call: (8) like(hanako, _G313) ?」と表示されたとき、「Enterキー」を押すと上記のように「creep」となり、処理が1歩すすむ。変数Xが「_G313」と表現されている。

「Exit: (8) like(hanako, apple) ?」と表示されたとき、変数Xに apple がバインドされている。

「Call: (8) like(hiroko, apple) ?」と表示されているのは、X=apple として、質問の「like(hiroko,X)」の部分が表示されている。

「Fail: (8) like(hiroko, apple) ?」とは、この質問が「No」であることを表す。

「Redo: (8) like(hanako, _G313) ?」となっているのは、バックトラックが生じて、最初の質問に戻ってきたことを表す。

「X = orange」と表示されたとき、「;」を押すと、バックトラックが生じて別の解を探索しはじめる。

□ 練習1

list1301.pl を用いて次の質問をしよう。trace を用いて様子を観察しよう。

  1. hanako と hikari が共に好きな物を質問しよう。
  2. hanako と hiroko と hikari が共に好きな物を質問しよう。

■ おちぼひろい

Prolog には他にも色々と操作できることがある。以下を読みながら、動作を確認しよう。

□ 算術演算

「is」を使うことで、計算をすることができる。 

% 以下は Prolog 上での動作確認
?- X is 1 + 2.
X = 3

□ カットオペレータ

カットオペレータは「!」で記述する。これは、バックトラックできないことを表す。

たとえば、hanako と hiroko が共に好きな物がわかったとき、その答えを固定して後の処理をさせるには、以下のように質問する。 

% 以下は Prolog 上での動作確認
?- trace.    (様子を見るため)
[trace] ?- like(hanako,X), like(hiroko,X), !, like(hikari,X).

カットオペレータを通過した後は、カットオペレータの左に戻れないことが分かるだろう。

□ 強制失敗(fail)

失敗の述語「fail」は、必ず失敗することを表す。

たとえば、A さんの嫌いなものを表す規則hateを以下に作成しよう。A さんの好きなものでないものは嫌いなものとすると以下のようにできる。 

% list1301.pl に追加
hate(A,X) :- like(A,X), !, fail.
hate(_,_).

% 以下は Prolog 上での動作確認
?- hate(hanako,apple).
false

?- hate(hanako,melon).
true

□ 高階呼出し

Prolog も、高階関数のように変数に質問をバインドできる。

以下の例では、変数 P に質問がバインドされている。P を質問することで、「like(hanako,X)」を質問したことになっている。 

% 以下は Prolog 上での動作確認

?- P=like(hanako,X), P.
P=like(hanako,apple),
X=apple

□ 否定

強制失敗と高階呼出しを使うと、否定の論理を扱うことができる。 

% list1301.pl に追加
not(P) :- P, !, fail.
not(_).

% 以下は Prolog 上での動作確認
?- not(like(hanako,melon)).
true.

□ 全解探索

findall(E,P,B) という組み込みの述語を使うことで、該当するデータを集めることができる。

引数の後から説明する。B は、集めた結果を格納する変数である。P は集める条件である。E は B に格納する要素の形式である。 

% 以下は Prolog 上での動作確認

?- findall( X, like(hikari,X), B ).
B = [apple, lemon]

?- findall( obj(X), like(hikari,X), B ).
B = [obj(apple), obj(lemon)]

?- findall( X, (like(hanako,X), like(hiroko,X)), B ).
B = [orange, lemon]

■ 総合問題

(1) size(L,N) 　　リストが与えられたとき、その長さを返す述語 size(L,N) を作成せよ。ヒント： L が [] のとき、N = 0 である。L が 1つ以上の要素からなるリストであるとき、L の2番目以降の要素からなるリストの長さに 1 を加えたものが、全体の長さである。

(2) list-cat(L1,L2,L3) 　　2つのリスト L1 の後ろに L2 を接続したものがリスト L3 であることを表す規則 list(L1,L2,L3)を作成せよ。ヒント：L1 が [] のとき L2 と L3 は同じである。L1 の2番目以降の要素からなるリストとL2を接続したものをL4とするとき、L3はL1の先頭要素とL4からなるリストである。

(3) list-refer(L,N,E) 　　リストLと数値Nが与えられたとき、N番目の要素は E であることを表す規則list-refer(L,N,E)を作成せよ。

(4) list-set(L1,N,D,L2) 　　リストL1と数値Nと要素Dが与えられたとき、L1のN番目の要素をDに置き換えたリストがL2であるという規則list-set(L1,N,D,L2)を作成せよ。

(5) list-position(L,E,N) 　　リストLと要素Eが与えられたとき、Lの中でEが最初に出現した番目Nを返す規則list-position(L,E,N)を作成せよ。なお、E は L に必ず存在することを前提とせよ。

(6) uniq(L1,L2) 　　リストL1が与えられたとき、L1から重複する要素を取り除いたリストL2を出力する述語 uniq(L1,L2) を作成せよ。ヒント：L1が [] のとき、L2 は [] である。L1=[A|L] とするとき、もし、AがLに含まれる(member)ならば、Lから重複を除いたリストがL2である。そうでなければ、Lから重複を除いたリストとAからなるリストがL2である。なお、実行の際、「?- uniq([a,b,c,a],X).」による解がただ一つであるようにしよう。

(7) list1301.pl にて、like(A,B) のうち、A に該当する要素で構成されるリストを、findall を用いて作成せよ。

(8) list1301.pl にて、like(A,B) のうち、B に該当する要素で構成されるリストを、findall を用いて作成せよ。

(9) (7)と(8)にて、重複のないリストを作成せよ。

豆知識

Ｑ. 演習の Web ページを家に帰ってからも読むには？

Ａ．演習室で、Web ページをダウンロードし、メモリスティックに入れて、家に持ち帰ってください。

以下を Linux コンソール上で実行してください。

wget -r http://unicorn.ike.tottori-u.ac.jp/tokuhisa/himitsu/200904-enshu3m/

unicorn.ike.tottori-u.ac.jp というディレクトリができるので、そのファイル一式を持ち帰ってください。

Ｑ．Windows の SWI-Prolog で日本語を使うには？

Ａ．Windows の SWI-Prolog では、UTF-8 という文字コードを使うことで日本語が使用できます。

UTF-8を用いたプログラムファイル：まず、Prolog のプログラムファイルを、「メモ帳(Notepad)」で開きます。次に、「名前を付けて保存」を選択します。次に、ウインドウの一番下に「文字コード(E)」という枠があるので、そこで「UTF-8」を選択します。

(c) 2009.7.6 by tokuhisa