第13回 差分リストを使ったプログラミング

今日の課題

■差分リスト

プログラムでリストを扱うとき、リストの中身全体が必要というわけではない。リストの中身を次のように、区別してみよう。 

（リスト全体） = ［ 扱いたい部分 ｜ 扱いたくない部分 ］ ...................(1)

差分リストは、「リスト全体」と「扱いたくない部分」を捉えたデータ構造である。記述形式は、Prolog ではかなり自由度がある。本演習では、次のようにする。 

〈リスト全体〉-〈扱いたくない部分〉

例題１

単語で構成されるリストを解析し、単語や熟語を判定するための辞書を、差分リストを用いて作成しよう。

下記の例の最初の事実で、差分リストになっているのは、[texas|R]-R である。この事実は、テキサスかどうかを判定する事実であるので、単語リストのうち、先頭の１単語が「texas」であることを扱いたい。しかし、それ以降のリストは扱いたくないため、変数 R としている。

「new york」は２単語であり、[new,york|R]-R という差分リストを用いている。 

（プログラム）
% list1301.pl

noun([texas|R]-R,n(texas)).
noun([kansas|R]-R,n(kansas)).
noun([new,york|R]-R,n(new_york)).
noun([north,dakota|R]-R,n(north_dakota)).
noun([south,dakota|R]-R,n(south_dakota)).
noun([new,mexico|R]-R,n(new_mexico)).
noun([washington|R]-R,n(washington)).

差分リストを使った質問の例を以下に示す。 

（質問）
＊その１
?- noun([texas]-A,N1).
＊その２
?- noun([kansas,texas,washington]-A,N1),noun(A-B,N2),noun(B-C,N3).
＊その３
?- L = [new,york,new,mexico,kansas,north,dakota,washington,south,dakota],
|      noun(L-A,N1),
|      noun(A-B,N2),
|      noun(B-C,N3),
|      noun(C-D,N4).

変数 N1、N2、… に、地名がバインドされていることを確認しよう。

リストのうち、扱わない部分を表す変数に何がバインドされているか確認しよう。たとえば、変数 A、B、C、D である。

その３では、noun(L-A,N1) を実行する段階では A は扱わない部分である。しかし、noun(A-B,N2) を実行する段階になると、A の中から単語を取り出すことになるので、A はリスト全体であり、B が扱わない部分となる。

また、その３では、リスト全体のうち、４つぶんの名詞が抽出されている。抽出されなかった残りの部分は変数 D に残されていることを確認しよう。

例題２

品詞ごとの辞書を用意しよう。そして、名詞のかたまりを抽出しよう。 

（プログラム）
% list1302.pl

noun([texas|R]-R,n(texas)).
 - - -（list1301.plと同様）- - -
noun([new,mexico|R]-R,n(new_mexico)).
noun([washington|R]-R,n(washington)).

noun([book|R]-R,n(book)).
noun([pen|R]-R,n(pen)).
noun([office|R]-R,n(office)).

noun([school|R]-R,n(school)).
noun([church|R]-R,n(church)).

noun([i|R]-R,n(i)).

det([the|R]-R,det(the)).
det([a|R]-R,det(a)).
det([an|R]-R,det(an)).

aj([good|R]-R,aj(good)).
aj([bad|R]-R,aj(bad)).
aj([new|R]-R,aj(new)).
aj([old|R]-R,aj(old)).
（質問）
＊その１
?- E1 = [a,pen],
|      det(E1-E2,D),
|      noun(E2-E3,N).
＊その２
?- E1 = [a,new,book],
|      det(E1-E2,D),
|      aj(E2-E3,A),
|      noun(E3-E4,N).
＊その３
?- E1 = [new,york,where,i,have,ever,lived],
|      noun(E1-E2,N).




　

練習１

上記の質問のその１、その２、その３を基にして、英語の名詞のかたまり（名詞句 Noun Phrase と言う）の規則を書いてみよう。ただし、その規則は次のように使えるようにしよう。 

?- E1 = [a,new,book],
|    np(E1-X,NP).

E1 = [a, new, book]
X = []
NP = np(det(a),aj(new),n(book))

Yes

■ バックトラック

Prolog は、質問に対する答えを求めて、規則の適用を試行錯誤している。

仮りに規則を適用し、途中で辻褄が合わなくなると、その仮りの適用をとりやめて、別の規則を適用することがある。これをバックトラックという。

練習１ができた人は次の規則を持っているだろう。 

np(E1-X,np(N)) :- noun(E1-X,N).
np(E1-X,np(D,N)) :- det(E1-E2,D), noun(E2-X,N).
np(E1-X,np(D,A,N)) :- det(E1-E2,D), aj(E2-E3,A), noun(E3-X,N).

ここで、次の質問をすると、Prolog はどのように動作するだろうか？ 

?- E1=[the,new,book], np(E1-X,NP).

  1. まず、1行目の np の規則を使う。
  2. noun(E1-X,N) を試みるが失敗する。
  3. 次に、１行目の np の規則を使うことを止め、２行目の np の規則を使う（バックトラックが発生している）。
  4. det(E1-E2,D) を試みると成功する。（変数には分かる範囲で値がバインドされているが、ここでは変数名のままで、略記する。）
  5. noun(E2-X,N) を試みるが失敗する。
  6. det(E1-E2,D) で別の解を探すが失敗する（バックトラックしている）。
  7. 次に、３行目の np の規則を使う（バックトラックしている）。
  8. det(E1-E2,D) を試みると成功する。
  9. aj(E2-E3,A) を試みると成功する。
  10. noun(E3-X,N) を試みると成功する。
  11. ３行目の np の規則は成功する。
  12. 結果が出力される。

トレースを実行すると、その様子がわかる。具体的には次のように実行する。 

?- trace.

Yes
[trace]  ?- E1=[the,new,book], np(E1-X,NP).
  Call: (9) - - -
  - - -（以降は自分で確認しよう）- - -
  - - -
[debug]  ?- nodebug.

Yes
?-

■ 練習２

英語の簡単な文法規則をプログラムにしてみよう。

名詞句 np の規則は上述した。その他のかたまりとして、動詞句 vp (Verb Phrase) や前置詞句 pp (Prepositional Phrase) がある。たとえば、“buy the book”は動詞句、“in the store”は前置詞句である。それぞれ名詞句に品詞（動詞や前置詞など）を追加した規則で定義できる。 

pp(E1-X,pp(P,NP)) :- preposition(E1-E2,P), np(E2-X,NP).
preposition([in|R]-R,p(in)).

さらに、英語の文 s (Sentence) は、名詞句と動詞句などの組み合わせで定義できる。

そこで、次の文が解析できるように、単語辞書と文法規則を作成せよ。

課題文
i bought new books
he went to mexico by bicycle
i read the book about new mexico 

（質問の例）
?- E=[i,bought,new,books], s(E-[],S).

(c) 2007.7.10 by tokuhisa