Hatena::Groupbugrammer

蟲!虫!蟲!

Esehara Profile Site (by Heroku) / Github / bookable.jp (My Service)
過去の記事一覧はこちら

なにかあったら「えせはら あっと Gmail」まで送って頂ければ幸いです。
株式会社マリーチでは、Pythonやdjango、また自然言語処理を使ったお仕事を探しています

 | 

2013-05-25

[]ごくごく普通のプログラマーが書くPrologのプロローグ 09:02

はじめに

 というわけで、金曜日からずっとPrologをやっていた。やったきっかけとしては、Amazonで某書が200円で売っていたから、衝動買いをしたのがきっかけだった。で、本が届いたので丁度いい機会だね、ということでPrologをやっていたのだが、これがやたらめったら面白い。某書自体はあまり面白くはないので薦めないんだけど(失礼!)、Prolog自体は面白いので、この機会に何が面白いのか、的な話をメモしておこうと思う。ちなみに、三段論法とかその辺りの話に関しては、どのProlog入門サイトにも載っているので、それを参考にするとして、この記事では、俺が詰まった部分について、ちょっとメモがてら書いておきます。

 ちなみに、処理系GNU Prologを使っています。またはSWI-Prologを使ったりするようです。

Hello!! World

 新しい言語をやるのなら、まずHello World!!を書くべきだよね、ということになるわけで、Pythonだったり、RubyならirbPHPならオプション"-a"といったように、対話型コンソールが付いている。Prologも、インストールしてコマンドを叩けば、対話型シェルが動くんだけれども、最初は味気ない下のような文字列が出ている筈だ。

 | ?-

 なんだこれは?という感じだけれども、これは「質問」みたいなものだ。Prologを書いて、ファイルを読み込ませれば、ここに質問を書いてあげれば、答えが返ってくる。で、どうやらPrologというのは「モノ」と「モノ」の関係を記述するのに向いているらしく、皆が皆、こぞって家系図を入門にしていたりする。

 だがまて。家系図は確かにPrologらしさではあるが、ちょっと面白みに欠ける。普通だったら、ファイルに処理を書いて、それを読み込ませて、表示させるというのが順当だと思う。このStack Overflowからコードを見てみると、次のような感じになっている。

:- initialization(main).
main :- write('Hello World!'), nl, halt.

 とりあえず、こういう風に書けば、世界が自動的にやってきてくれる。ちなみに、nlは改行の意味らしく、haltは終了で、対話型シェルのときにも使う。で、最後にピリオド。ピリオドは、条件部(mainの左側のこと)の終了を示してくれる。

 さて、Hello, Worldが終わったので、次は「P01」を早速解いてみることにする。

P01を解くまでの長くてつらい道のり

 Prolog Problems - Prolog Siteという、P-99の名前でも知られており、L-99(Lisp用)やH-99(Haskell用)という派生まで出来ている、人気の問題集である。で、この問題集の最初の問題は、「リストの最後を取り出せ」というものだ。Prologのリストは[]を使う。

 で、節にも書いた通り、このP01は、自分みたいな頭悪い人間だと、とんでもなく時間がかかった。というのも、Prologというのは、手続型、関数型とはまだ別の、違った癖がある言語だからだ。で、どんな癖があるのか。例えば、普通、プログラムといったら関数を使う。関数といったら何かといったら、何かしらのインプットをしたら、結果を返してくれるものだ。例えば、Haskellであるならば、下のように書ける。

plus_one::Int -> Int
plus_one x = x + 1

 で、当然のことながら、この関数を使う時は "plus_one 3"みたいに、値か何かを渡すのが当たり前に感じてしまう。実際、自分もそうだった。ところがだ、Prologは違う。Prologは、上記に書いた通り、「質問」することになる。質問した結果を返してくれる。例えば、Prologに「二つの数を足してもらう」という場合は、下のように書き、実行する。(ちなみに、対話型シェルから入力したい場合は、「[user].」と入力すると、その場でプログラムができるようになる。戻る時は「Ctrl + D」を使う)

plusone(X, Y) :- X is Y + 1.

| ?- plusone(X, 2)

X = 3

yes

 Prologと他の言語にちょっとした違いがあるとするならば、「条件に当てはまるもの」を探しだす役割があるということだ。上記の場合でも、Xをわざわざ指定するのは、「X is Y + 1」で、かつ「Y = 2」を満たす場合の「X」は何なのか、ということを「推論」する。つまり、発想が逆で、「これを与えたらこの結果になる」ではなく、「この結果にするためには、どのような条件が必要か」という逆算をする必要がある。

 例えば、Haskellでリストの最後の要素を取り出す場合は、再帰を使う場合、次のように書ける。

my_last :: [a] -> a
my_last (x:xs)
    | null xs = x
    | otherwise = my_last xs

 簡単に言ってしまえば、リストの先頭を取り出し([a, b, c, d] であるならば、a と [b, c, d] になる)、リストに残りが何もなければ、取り出したものが最後の要素だから、それを返せばよい。

 しかし、これを素朴に信じて実装すると痛い目を合う。実際に自分がドハマりしたコードを掲載してみる。

error_last(LAST, []).
error_last(LAST, [CAD|CDR]) :-
    [CAD|CDR] \== [],
    error_last(CAD, CDR).

 ちなみに、一番最初の行は、こういう組み合わせは真である、というだけの宣言だ。さて、これを動かしてみると、確かに全体はtrueになるのだが、肝心のLASTがでてこない。こういうときは、「Ctrl+C」で"t"(traceのこと)をするとわかりやすい。

| ?- error_last(LAST, [a, b, c, d]).
      1    1  Call: error_last(_17,[a,b,c,d]) ? 
      2    2  Call: [a,b,c,d]\==[] ? 
      2    2  Exit: [a,b,c,d]\==[] ? 
      3    2  Call: error_last(a,[b,c,d]) ? 
      4    3  Call: [b,c,d]\==[] ? 
      4    3  Exit: [b,c,d]\==[] ? 
      5    3  Call: error_last(b,[c,d]) ? 
      6    4  Call: [c,d]\==[] ? 
      6    4  Exit: [c,d]\==[] ? 
      7    4  Call: error_last(c,[d]) ? 
      8    5  Call: [d]\==[] ? 
      8    5  Exit: [d]\==[] ? 
      9    5  Call: error_last(d,[]) ? 
      9    5  Exit: error_last(d,[]) ? 
      7    4  Exit: error_last(c,[d]) ? 
      5    3  Exit: error_last(b,[c,d]) ? 
      3    2  Exit: error_last(a,[b,c,d]) ? 
      1    1  Exit: error_last(_17,[a,b,c,d]) ? 

 いわゆるLASTの借りの置き場みたいなのが「_17」なのだが、この部分が何かの値に書き換わらないと、LASTが何になるのか決定されないということだ。でも、どうもこのログをみる限りだと、最後の階層まで到達しているわけだから、再帰としては問題がなさそうに見える。

 例えば、じゃあということで、次のように改変してみる。

get_error_last(LAST, CACHE, []) :- LAST = CACHE.
get_error_last(LAST, CACHE, [CAD|CDR]) :-
    [CAD|CDR] \== [],
    get_error_last(LAST, CAD, CDR),
    LAST is CACHE.

error_last(LAST, [CAD|CDR]) :-
    get_error_last(LAST, CAD, CDR).

 大文字のものは変数として扱われるので、最後に代入してあげればいい。これで一応、動くことは動くのだが、代入を排除して、もっとPrologっぽく書きたい、というのがあるかもしれない。

get_last(_CACHE, _CACHE, []).
get_last(LAST, CACHE, []) :-
    get_last(CACHE, CACHE, []),

get_last(LAST, _, [CAD|CDR]) :-
    [CAD|CDR] \== [],
    get_last(LAST, CAD, CDR).

my_last(LAST, [CAD|CDR]) :-
    get_last(LAST, CAD, CDR).

 最後で、LASTを_CACHEとして書き換えるのを最後の条件とすると、必然的にこれらの整合性をとるためには、LASTはCACHEと同じにならなければならない。ここでLASTはCACHEと一緒であると推論され(てるのかな?自信無い)、無事最後のリストの文字が届くようになる。

まとめ

 ずいぶんと長い記事になってしまった。今回は、あえて自分が「Prologすごい!」って思った部分を重点的に書いてみた。ちゃんとした理解に関しては、他の入門サイトに腐るほどあるので、むしろ初学者としてハマってしまったところを共有したほうが、「変さ」というか「癖」みたいなものが伝わってくるかなと思って、そういう記事にしてみました。Prologは、ちょっと面白いので、もう少しいじろうかなと思っています。

もっと詳しくは?

本の紹介

 |