prologに挑戦 - 初学者の箸置

http://sourceforge.jp/projects/descartes/wiki/FrontPage
デカルト言語のwikiにプログラム例が載ってて「prologみたいな感じ」的な説明でappendが出ていた。僕はprologっていうと、なんか人工知能の話とかで推論がどうのこうのとか、バックトラックがキーワードとか、そんなことを知っている程度で、ほとんど知らない。関数型をちょいちょい弄ってきたお陰でなんとなくはわかるんだけど、どうしても意味がわかーらん。

append(Z, [], Z).
append( [W | Z1], [W | X1], Y) :- append(Z1, X1, Y).

２つあるのはパターンマッチングか、とかわかるんだけど、次がいみふ。書き方としてはhaskellやerlangみたくcar, cdrが書いてあるんだろうと思われるんだけど何で第一第二引数が同じWを含んでるんだろう、とかなんで両方ともcdrだけ再帰してるんだとか悩み始める。使い方を見てみて少しわかり始めてくる。どうやら第一引数が返り値になるようだ。なるほど。
つまり１番目の入力リストのcarが返り値の頭にくっつく、と。で、後ろの:-以降のが。。。とか考えていて超混乱状態に陥る。
これはパラダイムからして理解できてないのが原因なので、急がば回れ、なんとなく今まで敬遠していたprologを勉強する気になる。

事実データベース

一階述語論理って言うとややこしそうに見えるけど、単に述語が変項（変数）じゃない事実データベースとその照合、という理解をした。変項化すると二回述語論理。
変項にいろいろ当てはめて関係プログラミングができる。。。とはじめてみると面白すぎる。もっと早く勉強しておくんだった。事実を"述語(名前)"のように書いて表現する。よくあるパターンだと「AはBが好きだ」を"like(A,B)"とか。

like(tkuro, python).
like(tkuro, perl).
like(tkuro, vim).
like(yukichanko, perl).
like(yukichanko, skill).  /* really? */

とかしておいて、

?- like(yukichanko, perl).

Yes

?- like(tkuro, fortran).

No

?- like(Y,perl).　/*変数を利用して関係マッチング*/

Y = tkuro ;

Y = yukichanko ;

No

みたいな感じ。
「規則」を定義することもできる。

述語(変項) :-  goal_1, .... goal_n.

のように書くと、全部のゴールが満たされたら述語がYESとなる。
たとえばリストの最小値だったら、

min(A, [A]).
min(C, [C|D]) :-
  min(E,D),
  C < E.
min(E, [C|D]) :-
  min(E,D),
  C >= E.

のようにすると、ゴールがすべて満たされるほうの min()が選ばれて、結果最小値が第一引数のところに入る。

?- min(Which, [5,4,3,1,3]).

Which = 1 

Yes

グラフ色塗り問題をやってみる

/* 
  1------2
  |      |
  +-+-+  |
  | | |  |
  3-4-5--+
  |      |
  +------+
 */
adj(1,2).
adj(1,3).
adj(1,4).
adj(1,5).
adj(2,3).
adj(2,5).
adj(3,4).
adj(4,5).

adjacent(A,B):- adj(A,B).
adjacent(A,B):- adj(B,A).

color(paint1, 1, red). 
color(paint1, 2, blue).
color(paint1, 3, green).
color(paint1, 4, yellow).
color(paint1, 5, purple).

color(paint2, 1, white).
color(paint2, 2, blue).
color(paint2, 3, green).
color(paint2, 4, yellow).
color(paint2, 5, blue).

conflict(Paint, X,Y) :-
  adjacent(X,Y),
  color(Paint, X, Color),
  color(Paint, Y, Color).

?- conflict(paint1, X,Y).

No
?- conflict(paint2, X,Y).

X = 2
Y = 5 ;

X = 5
Y = 2 ;

No

ちょっと兄さんこれ面白すごろく。

appendの解釈

というわけでappend再考。

append( [W | Z1], [W | X1], Y) :- append(Z1, X1, Y).

は、入力：リスト１のcdr =X1, と入力：リスト２=Yをアペンドしたもの = Z1を作って、それを入力：リスト１のcar = Wの後ろにくっつけている、というわけだ。なるほど理解。

結論

仕事中に何やってんだだめ社員め