7つの言語7つの世界 第4章 Prolog 1-3 日目セルフスタディやってみた

７つの言語 ７つの世界 第4章 Prolog 1-3 日目のセルフスタディやってみました。Prolog を触るのは今回が初めてだったのですが、やっていて楽しかったです。もっとやりたいかと聞かれれば、もういいですと答えますけど。

Prolog のインストール

例によって、セルフスタディにかけた時間よりも、インストールに費した時間のほうが長かったです。

→MacPorts の gprolog 1.4.0 で Segmentation Violation - passingloopの日記

1 日目

探してみよう

無償の Prolog チュートリアル

いくつか見つかりますが、Introduction to Prolog (in Japanese) がおすすめです。

サポートフォーラム(複数ある)

日本語のサポートフォーラムはどこにあるんだろう?

Prolog のオンラインリファレンス(自分が使っている処理系に合ったものを選ぶこと)

GNU Prolog のオンラインリファレンスは、GNU-Prolog Manual.

試してみよう

自分のお気に入りの本と作家を表す簡単な知識ベースを作成せよ.

はてダのスーパー pre 記法が prolog をサポートしていることを知りました。

publish(arai_motoko,hitome_anatani).
publish(hoshi_shinichi,bokko_chan).
publish(ito_keikaku,harmony).
publish(komatsu_sakyo,nippon_chinbotsu).
publish(tsutsui_yasutaka,toki_wo_kakeru_shojo).
publish(tsutsui_yasutaka,paprika).
publish(tsutsui_yasutaka,nanase_futatabi).
publish(yumeno_kyusaku,dogura_magura).

作成した知識ベースから特定の作家の著作をすべて検索せよ.

コマンドラインから gprolog を実行して検索します。

% gprolog 
| ?- ['favorites.pl'].

(1 ms) yes
| ?- publish(tsutsui_yasutaka,What).

What = toki_wo_kakeru_shojo ? a

What = paprika

What = nanase_futatabi

yes

音楽家と楽器を表す知識ベースを作成せよ.また,音楽家と音楽のジャンルを表す知識ベースも作成せよ.

これも、はてダのスーパー pre 記法で貼り付けてみます。

play(coba,accordion).
play(bruce_hornsby,accordion).
play(bruce_hornsby,piano).
play(hakase_taro,violin).
play(senju_mariko,violin).
play(sakamoto_ryuichi,piano).
play(matsumoto_takahiro,guitar).
play(sergio_assad,guitar).
play(muraji_kaori,guitar).

genre(coba,soundtrack).
genre(bruce_hornsby,jazz).
genre(bruce_hornsby,rock).
genre(hakase_taro,classic).
genre(hakase_taro,soundtrack).
genre(senju_mariko,classic).
genre(sakamoto_ryuichi,piano).
genre(sakamoto_ryuichi,soundtrack).
genre(matsumoto_takahiro,rock).
genre(matsumoto_takahiro,jpop).
genre(sergio_assad,tango).
genre(muraji_kaori,guitar).

ギターを演奏するすべての音楽家を検索せよ.

これも、gprolog で検索します。

% gprolog
| ?- ['musicians.pl'].
(1 ms) yes
| ?- play(Who,guitar).

Who = matsumoto_takahiro ? a

Who = sergio_assad

Who = muraji_kaori

yes

2日目

探してみよう

フィボナッチ数列と階乗計算の実装.動作方法を説明せよ

まずはフィボナッチ数列から：

  • 2行目: Fib(0) = 0
  • 3行目: Fib(1) = 1
  • 4行目: Fib(N) = F の F を求めるには、
  • 5行目: N > 1 のとき、
  • 6行目: N1 = N - 1,
  • 7行目: N2 = N - 2 とすると、
  • 8行目: F1 = Fib(N1),
  • 9行目: F2 = Fib(N2) として求められた F1, F2 を使って、
  • 10行目: F = F1 + F2 とすればよい。

つぎに階乗計算：

  • 2行目: 定義 Fact(0) = 1
  • 3行目: F = Fact(N) の F を求めるには、
  • 4行目: N > 0 のとき
  • 5行目: N1 = N - 1 なる N1 について
  • 6行目: F1 = Fact(N1) を求め、
  • 7行目: F = F1 * N とすればよい。
少し高度な問題に取り組んでみたいなら,次の問題に挑戦してみるとよい.

ハノイの塔を実装し,その動作方法を説明せよ.

ハノイの塔とは何かを調べるために、Tower of Hanoi - Wikipedia を読んでいたら解き方も載っていたので、そのまま実装しました：

プログラム中の hanoi(N, A, B, C) は、A にある N 枚のディスクを B に移動させることを意味しています。

  • 2行目: N = 0 のとき、つまり、ディスクが無いときは何もしなくてもいいと言っています。
  • 3-4行目: N > 0 のときの hanoi/4 は、
  • 5行目: N1 = N - 1 として、
  • 6行目: まず、N1 枚のディスクを A から C に動かして、
  • 7行目: 次に、N 枚目のディスクを A から B に動かす（動かしたこと write する。nl は改行）
  • 8行目: そして、C にある N1 枚のディスクを B に動かすことで実現される。

これを実行してみると、

% gprolog 
GNU Prolog 1.4.0
By Daniel Diaz
Copyright (C) 1999-2011 Daniel Diaz
| ?- ['tower_of_hanoi.pl'].
yes
| ?- hanoi(3, rod1, rod2, rod3).
move,1,from,rod1,to,rod2
move,2,from,rod1,to,rod3
move,1,from,rod2,to,rod3
move,3,from,rod1,to,rod2
move,1,from,rod3,to,rod1
move,2,from,rod3,to,rod2
move,1,from,rod1,to,rod2

true ?

となります。

「not」(~でない)という表現を扱うときの問題点を指摘せよ.Prolog では否定表現に気をつけなければならないが,それはなぜか.

Google 先生に聞いてみると、Prolog の否定 \+ は論理否定ではなく失敗としての否定 (negation as failure) であることがわかりました。

  • あるゴールの否定は、あるゴールの証明が失敗すること
  • 否定のゴールの中に変数を含むときに問題が起こりえること

までは書いてあったのですが、文章を見てもよくわからなかったので、例を作ってみました。

飛ばない鳥はペンギンだという推論です。これを実行すると、

% gprolog 
GNU Prolog 1.4.0
By Daniel Diaz
Copyright (C) 1999-2011 Daniel Diaz
| ?- ['penguin.pl'].

(1 ms) yes
| ?- penguin1(X).

no
| ?- penguin2(X).

X = kiwi ? 

yes
| ?-

となり、penguin2/1 は想定通りに推論できるのですが、penguin1/1 は何も見つけられません。

これは、pengin1/ では 7行目の fly(X) が X = duck で証明されてしまい、失敗しないからです。penguin2/ の場合、bird(X) で X = kiwi か X = duck となるので、X = kiwi のとき fly(X) の証明に失敗することができます。サブゴールの順番にも気をつける必要があるということですね。

試してみよう

リストの各要素を逆順に並べよ.

GNU Prolog の reverse/2 を使います。

% gprolog
GNU Prolog 1.4.0
By Daniel Diaz
Copyright (C) 1999-2011 Daniel Diaz
| ?- reverse([a, b, c], X).

X = [c,b,a]

yes
| ?-

リスト内で最も小さな要素を見つけよ.

実行結果：

% gprolog
GNU Prolog 1.4.0
By Daniel Diaz
Copyright (C) 1999-2011 Daniel Diaz
| ?- ['min.pl'].

(1 ms) yes
| ?- min(X, [5, 2, 7, 4, 9]).

X = 2 ? 

yes
| ?-

リスト内の要素をソートせよ.

GNU Prolog の sort/2 を使います。

% gprolog
GNU Prolog 1.4.0
By Daniel Diaz
Copyright (C) 1999-2011 Daniel Diaz
| ?- sort([3, 1, 5, 2, 0], S).

S = [0,1,2,3,5]

yes
| ?-

これは簡単なのですが、前段で min/2 を作っているので選択ソートも作ってみました。

3日目

探してみよう

Prolog には,入出力機能もいくつか用意されている.変数を出力する述語 print を見つけよ.

→ http://www.gprolog.org/manual/gprolog.html#htoc163

print を用いて正しい答えだけを出力する方法を考えよ.この述語はどのような 方法で動作しているか?

これは次の試してみようでやってみる。