Prolog言語を使ってみよう

最近は、スクリプト言語として、webで使える、PHP、RubyやPythonが流行である。
少し前には、Perlが流行ったが、これは、awk式文法やら、C言語的な書き方やら、にせオブジェクト指向や、なんでも取り込んだ言語である。私は節操がないところが好きである。
またもう少し古くなると、Lispやエディタemacsのプログラミングに使う、elispなどがある。

1980年代、コンピュータ産業や家電で世界の先端を行く国家プロジェクトとして、人工知能を作ろう、並列コンピュータを作ろうという、第五世代コンピュータプロジェクト http://bit.ly/KL2WoP があった。その主力言語が、Prologという言語である。

Prolog) 
私は、専門家ではないが、Prologにはユニフィケーションという強力なパタンマッチ機能があり、バックトラックという自動やり直し機能と組み合わせて、プログラムが極めて短くエレガントにかける。バックトラックを中断させる、カットという機能もあるが、これを多用し出すとprologらしくはなくなる。

http://ja.wikipedia.org/wiki/Prolog　にPrologの分かりやすい紹介がある。他のどのスクリプト言語とも違った言語である。

コンピュータ言語を学ぶ早道）
言語を学ぶには、本で勉強しても退屈である。無料の処理系が、ネットにころがっていて、ググると出てくるので、インストールして、サンプルプログラムを書いてみたり、実験するのが一番早道である。「習うより慣れろ」である。大体、そのほうが圧倒的に楽しい。

処理系)
パソコンで動くprologの処理系は http://bit.ly/KKX92t　に、一覧がある。
そのうち、無料のSWI PrologをMac OS-X Lionにインストールしてみた。ダウンロードサイトには、windows(NT, XP, VISTA, win7)用もある。

http://blog.livedoor.jp/add20/archives/2354663.html　にやり方がある。具体的には、

1. http://www.swi-prolog.org/download/stable　から、Mac OS-X Lion用のSWI Prolog 6.0.2を入手
2. ダウンロードされたpkg拡張子のファイルをダブルクリックして、指示に従ってインストール
3. terminalウィンドウを開けて、http://blog.livedoor.jp/add20/archives/2354663.html　にあるやりかたで、パスを通す。具体的には、
   export PATH=$PATH:/opt/local/bin　を、~/.bashrc に書き込む。~ は、terminal windowで、cd とだけ打ち込んだときに移動するホームディレクトリである。
   
   ただし、

   2011年8月27日土曜日: Macでの.bashrcの編集

   に書いたように、Mac OS-Xのterminal windowは標準では、.bashrcを読み込まないので、~/.bash_profile　を変更しておく必要がある。

これで、インストールは終わり。terminal windowから、

swipl -f ファイル名　　と書くと、prologコードを書いたファイルが実行できる。swiplをぬけるときは、control-Dで良い。haltと言うメッセージがでるのは気持ち悪いが、prologの流儀なのであろうか。。

サンプルプログラムを実行してみよう)
Prologに再帰呼び出しを併用すると、プログラムが非常に短く書ける。
http://www.geocities.jp/m_hiroi/prolog/prolog04.html　に言語仕様の簡単な解説とともに、サンプルプログラムがある。これを実行してみた。
最終的なソースプログラムとswi prologでの実行結果を示す。

ハノイの塔）
wiki pedia　http://bit.ly/KL5mns　に4枚の板のときのハノイの塔を解く動画が出ている。簡単にいうと、1) 板を1枚ずつ棒から棒に移動する。2) 必ず自分より大きな板のうえにしか載せられない。3) 一つの棒に乗っかった板を、他の棒に全部移動する。というパズルである。

これは、再帰呼び出しによって実現する。4枚の板を移動するのは、3枚の板を移動する処理をして、一番大きな板を移動して、また3枚の板を上に戻せばよいからである。
つまり、

1. 板が1枚だけのとき、それを移動する処理は明白。
2. 板がN枚のときは、板がN-1枚のときの処理で前後をはさんで、一番したの板を移動させればよい。

と再帰を使うと極めて簡単に書ける。

swipl -f hanoi.swi 　とコマンドを打つ。?- というプロンプトが出るので以下の様に打ち込む。文末の ピリオド '.'は忘れてはならない。ピンクの部分がswi prologの返した結果である。終了したら、コントロールDと打つと、swi prologを抜ける。

打ち込んだ問題の意味は、4枚の板があって、板を通す筒はaとbとcと呼ぶという意味である。あとに解説する。

?- hanoi(4,a,b,c).
a to c
a to b
c to b
a to c
b to a
b to c
a to c
a to b
c to b
c to a
b to a
c to b
a to c
a to b
c to b
true .

上記wiki pediaの動画に、コレに対応する文字を入れると以下のようになる。棒BとCは、一方を最終目的地、一方をwork areに使う。上記プログラムは、最終移動先をBに持ってくるように書かれている（プログラムソース中のToになっている）。結果は、先にCに移動している。対応して棒の名前をつけた。

つまり、上記の結果は、こう読む。棒Aから一番上の板を棒Cに移動。aから板をbに移動。

とやっていくと、最後に板は全部棒Bに移動する。対応するプログラム、hanoi.swi　は以下のようなものである。たったの、5行である。4行はprologの1文(正確には、ホーン節)が複数行に分かち書きされているだけなので、実は2文である。最初の実行のところで、

実行時に、?- hanoi(4,a,b,c).　ではなく、?- hanoi(4,a,c,b).　といれると、上記の図の棒の名前をa,b,cの順につけたものと一致する。入力の順と図の順を一致させたければ、プログラムのToと Viaならびに_の位置を変えればよい。

プログラムは、まさに再帰読みだしを、そのまま書いている。1文目が、1枚のときの処理。FromをToに移動して、印刷している。Prologのformat文の書式が、なじみの無い形なので、違和感があるかもしれない。~a が文字で印刷。~n が改行を示す、format指定である。
2文目は、N枚の移動をN-1枚の移動ではさんだ、1枚の移動にして、1枚の移動で印刷をかけている。変数代入に　is　をつかうのがprologの流儀。と、簡単である。

---- hanoi.swi ----- 

hanoi(1, From, To, _) :- format('~a to ~a~n', [From, To]).
hanoi(N, From, To, Via) :-
        N1 is N - 1, hanoi(N1, From, Via, To),
        format('~a to ~a~n', [From, To]),
        hanoi(N1, Via, To, From).

------

クイックソート）
ソートは、めちゃくちゃに並んだ物体を所定の順に並び替えるものである。以下では、数値を小さい順に並び替えている。さまざまなソート手法（アルゴリズム）が提案されている　（wiki  http://bit.ly/KLeNTO　に紹介がある。）が、比較的高速でかつ、有名なものとしてクイックソートがある。

さまざまな視覚化サイトがあるが、たとえば、http://homepage.mac.com/mihailod/atic/sorting.html にある視覚化が分かりやすい。

swipl -f quick.swi 　と打ち込む。

?- quick([5, 3, 7, 6, 9, 10, 20], X).
X = [3, 5, 6, 7, 9, 10, 20] .

--- qucik.swi ---　これは、5文である。

quick([X | Xs], Ys) :-
        partition(Xs, X, Littles, Bigs),
        quick(Littles, Ls),
        quick(Bigs, Bs),
        append(Ls, [X | Bs], Ys).
quick([], []).
partition([X | Xs], Y, [X | Ls], Bs) :-
        X =< Y, partition(Xs, Y, Ls, Bs).
partition([X | Xs], Y, Ls, [X | Bs]) :-
        X > Y, partition(Xs, Y, Ls, Bs).
partition([], Y, [], []).

---
8クイーン)
チェスのqueen (縦横斜めが取れる)を8x8のチェス盤において、どのqueenもお互いをとらないように配置するパズルである。http://bit.ly/KLa04W　に説明がある。

swipl -f 8queens.swi と打ち込む。

?- queen_f(Q), write(Q), nl, fail.
[4,2,7,3,6,8,5,1]
[5,2,4,7,3,8,6,1]
[3,5,2,8,6,4,7,1]
[3,6,4,2,8,5,7,1]
[5,7,1,3,8,6,4,2]
[4,6,8,3,1,7,5,2]
中略
[6,3,5,7,1,4,2,8]
[6,4,7,1,3,5,2,8]
[4,7,5,2,6,1,3,8]
[5,7,2,6,3,1,4,8]
false.

解説）

http://bit.ly/KLa04W　にあるように、基本解は12個なのだが、これの回転と鏡像(点対称を除く)を含めた92個が結果として表示されている。ちょっとプログラムを改造すれば、下の盤面と行と列の並びをあわせ、基本解だけ抽出するように改造できるかもしれない。先のwikiから基本解の一部の図を引用しておく。

解1をprologの結果風に書くと、[2,4,6,8,3,1,7,5]となる。これを後ろから読む、(つまりaとhの名前の付け方を逆にしたもの)と、[5,7,1,3,8,6,4,2]となり、上記結果、上から5番目の回答と一致する。

--- 8 queens.swi ---　これは6文である。

queen_f(Q) :- queen_sub([1,2,3,4,5,6,7,8], [], Q).
queen_sub(L, SafeQs, Q) :-
        select(X, L, RestQs),
        not(attack(X, SafeQs)),
        queen_sub(RestQs, [X | SafeQs], Q).
queen_sub([], Q, Q).
attack(X, Xs) :- attack_sub(X, 1, Xs).
attack_sub(X, N, [Y|Ys]) :- (X =:= Y + N ; X =:= Y - N).
attack_sub(X, N, [Y|Ys]) :- N1 is N + 1, attack_sub(X, N1, Ys).

---