論理型言語Prologと関数型言語Haskellを比較してみた

PrologとHaskellで同じ問題を解いてみました。Prologで同程度の問題を解けるくらいのプログラミングができたのは初かもしれない…。

お題は鍋谷さんが開催されている「オフラインリアルタイムどう書く」の第4回のお題を利用させてもらいました。

テトロミノ認識～横へな 2012.10.6

わたしが回答した例はGitHubにもアップしてあります（このエントリで取り上げるコードもアップされています）。

mattsan/ord4tetroid ? GitHub

コードが、というか、そもそも解き方がアレでナニで不細工ですが、今回の話題の中心は別のところ――HaskellとPrologを比較してその違いを知りPrologの理解を深める――なので大目に見てください。

PrologとHaskellを比較する

コードの全体は後半にありますので適宜参照して頂ければと思います。

パタンから該当する文字を得る部分の比較

Haskellのばあい。

tetromino [ (0, 0), (0, 1), (0, 2), (1, 2) ] = "L"

Prologのばあい。うしろに載せたコードからちょっと改変してますが意味はほぼ同じです。

tetromino([ [0, 0], [0, 1], [0, 2], [1, 2] ], 'L').

似ているようで違う2つの式。Haskellの場合はコレコレのパタンのばあいは指定した値を返すと定義されているのに対し、Prologのばあいは第1引数と第2引数がコレコレのばあい式は成功する（真になる）と定義されています。

式の成否を判定するので次のように書くと、

?- tetromino(0,0], [0,1], [0,2], [1,2?, 'L').
true.

式が成功したという結果を返します。

ここで第2引数を変数にすると、次のように表示されます。

?- tetromino(0,0], [0,1], [0,2], [1,2?, R).
R = 'L'.

これは「式が成功する（真になる）ためには変数Rが'L'でなければならない」という主張していることなのだと思います（たぶん）。

なお、実際のPrologのコードでは末尾に「 :- !」という部分が付いていますが、これはパタンマッチをここで中断するという意味です。上の例のばあい「tetromino(_, '-').」にもマッチしてしてまうので（「_」はHaskell同様なににでもマッチするワイルドカードです）、中断しないと変数Rの値は'L'と'-'の2つあると表示されてしまいます。

文字列から座標（数値）への変換する部分の比較

文字列から座標（数値）への変換（文字列からの読み取り）部分では、違いがもっとはっきりします。

Haskellのばあい。

c2i = subtract 48.ord

str2pos [x0, y0, ',', x1, y1, ',', x2, y2, ',', x3, y3] =
  [(c2i x0, c2i y0), (c2i x1, c2i y1), (c2i x2, c2i y2), (c2i x3, c2i y3)]

Prologのばあい。繰り返しの式を分離できていないのは未熟なため。言及したいのは別のところなのでこのままでご勘弁。

str2pos([X00, Y00, C, X01, Y01, C, X02, Y02, C, X03, Y03], [[X10, Y10], [X11, Y11], [X12, Y12], [X13, Y13]]) :-
    X10 is X00 - 48,
    Y10 is Y00 - 48,
    X11 is X01 - 48,
    Y11 is Y01 - 48,
    X12 is X02 - 48,
    Y12 is Y02 - 48,
    X13 is X03 - 48,
    Y13 is Y03 - 48,
    C =:= 44.

Prologでは:-以降の部分（bodyと言います）に:-以前の部分（headと言います）が成立する条件が書かれています。bodyではコンマは連言を表します。ですので「headが成立する条件は『X10 is X00 - 48』かつ『Y10 is Y00 - 48』かつ『X11 is X01 - 48』かつ『Y11 is Y01 - 48』かつ『X12 is X02 - 48』かつ『Y12 is Y02 - 48』かつ『X13 is X03 - 48』かつ『Y13 is Y03 - 48』かつ『C =:= 44』」という意味になります。

該当する文字を取得するばあいと同じように、第2引数を変数にすると、式が成功するために必要な値を推論して変数に束縛します。

ちなみに第2引数に値を指定して第1引数を推論ことはできないのだろうかと考えられますが、式中のisは右辺側の値を推論することができないため第1引数を推論ことはできないようです。

連続する関数と項の連言

似て非なる部分。おそらく、実装という観点から考えると同じことをしていると思うのですが、考え方がかなり違う部分がここではないかと思います。Prolog プログラミングを始めた当初つまずいたのもこの部分。

Haskellのばあい（部分）。

tetromino.sort.normalize.str2pos

「（文字列を）str2posに入力して、その出力をnormalizeに入力して、その出力をsortに入力して、その出力をtetrominoに入力して、その出力を全体の出力としてえる」という意味です。

Prologのばあい（部分）。

str2pos(S0, P0), sort(P0, P1), normalize(P1, P2), tetromino(P2, R2)

Prologとして正しい表現かわかりませんが、このコードは理解としては「『str2pos(S0, P0)かつsort(P0, P1)かつnormalize(P1, P2)かつtetromino(P2, R2)』が真となるようなS0, P0, P1, P2, R2の組み合わせを推論する」ということになると思います。ここでS0は外部から与えられる文字列で、結果としてR2が出力としてえられることになります。

まとめ、あるいはProlog プログラミングのポイントは「なにが成り立てばよいか」と考えることではないかと（たぶん）

「ある『入力』に対してある『出力』を『得る』ために、『どうするか』を考える」のが手続き型。
「ある『入力』に対してある『出力』を『得る』ために、『どうあるか』を考える」のが関数型。
「ある『入力』とある『出力』の『関係が成立する』ためには、『なにが成立しなければならないか』を考える」のが論理型。

…と現在の理解を大雑把にまとめてみました。「入力から出力を得る」ということよりも「入力と出力の関係を成立させる」ということに意識を向ける必要があるようです。

とりあえず今回はそんな感じで。

以下コード。

Haskellのコード全体

import Data.Char
import Data.List

c2i = subtract 48.ord

str2pos [x0, y0, ',', x1, y1, ',', x2, y2, ',', x3, y3] =
  [(c2i x0, c2i y0), (c2i x1, c2i y1), (c2i x2, c2i y2), (c2i x3, c2i y3)]

normalize ps = foldl (\xs (x, y) -> (x - xmin, y - ymin):xs) [] ps
  where
    xmin = minimum $ map fst ps
    ymin = minimum $ map snd ps

tetromino [ (0, 0), (0, 1), (0, 2), (1, 2) ] = "L"
tetromino [ (0, 0), (0, 1), (1, 0), (2, 0) ] = "L"
tetromino [ (0, 0), (1, 0), (1, 1), (1, 2) ] = "L"
tetromino [ (0, 1), (1, 1), (2, 0), (2, 1) ] = "L"
tetromino [ (0, 0), (0, 1), (1, 1), (2, 1) ] = "L"
tetromino [ (0, 0), (0, 1), (0, 2), (1, 0) ] = "L"
tetromino [ (0, 0), (1, 0), (2, 0), (2, 1) ] = "L"
tetromino [ (0, 2), (1, 0), (1, 1), (1, 2) ] = "L"
tetromino [ (0, 0), (1, 0), (2, 0), (3, 0) ] = "I"
tetromino [ (0, 0), (0, 1), (0, 2), (0, 3) ] = "I"
tetromino [ (0, 0), (1, 0), (1, 1), (2, 0) ] = "T"
tetromino [ (0, 0), (0, 1), (0, 2), (1, 1) ] = "T"
tetromino [ (0, 1), (1, 0), (1, 1), (2, 1) ] = "T"
tetromino [ (0, 1), (1, 0), (1, 1), (1, 2) ] = "T"
tetromino [ (0, 0), (0, 1), (1, 0), (1, 1) ] = "O"
tetromino [ (0, 0), (0, 1), (1, 1), (1, 2) ] = "S"
tetromino [ (0, 1), (0, 2), (1, 0), (1, 1) ] = "S"
tetromino [ (0, 1), (1, 0), (1, 1), (2, 0) ] = "S"
tetromino [ (0, 0), (1, 0), (1, 1), (2, 1) ] = "S"
tetromino _                                  = "-"

main = getContents >>= putStrLn.unlines.map (tetromino.sort.normalize.str2pos).lines

Prologのコード全体

str2pos([X00, Y00, C, X01, Y01, C, X02, Y02, C, X03, Y03], [[X10, Y10], [X11, Y11], [X12, Y12], [X13, Y13]]) :-
    X10 is X00 - 48, Y10 is Y00 - 48,
    X11 is X01 - 48, Y11 is Y01 - 48,
    X12 is X02 - 48, Y12 is Y02 - 48,
    X13 is X03 - 48, Y13 is Y03 - 48,
    C =:= 44.

normalize([[X00, Y00], [X01, Y01], [X02, Y02], [X03, Y03]], [[X10, Y10], [X11, Y11], [X12, Y12], [X13, Y13]]) :-
    min_member(Xmin, [X00, X01, X02, X03]), min_member(Ymin, [Y00, Y01, Y02, Y03]),
    X10 is X00 - Xmin, Y10 is Y00 - Ymin,
    X11 is X01 - Xmin, Y11 is Y01 - Ymin, 
    X12 is X02 - Xmin, Y12 is Y02 - Ymin, 
    X13 is X03 - Xmin, Y13 is Y03 - Ymin.
normalize([_,_,_], [ [0,0], [0,0], [0,0], [0,0] ]). 
normalize([_,_],   [ [0,0], [0,0], [0,0], [0,0] ]). 
normalize([_],     [ [0,0], [0,0], [0,0], [0,0] ]). 

tetromino([ [0, 0], [0, 1], [0, 2], [1, 2] ], 'L') :- !.
tetromino([ [0, 0], [0, 1], [1, 0], [2, 0] ], 'L') :- !.
tetromino([ [0, 0], [1, 0], [1, 1], [1, 2] ], 'L') :- !.
tetromino([ [0, 1], [1, 1], [2, 0], [2, 1] ], 'L') :- !.
tetromino([ [0, 0], [0, 1], [1, 1], [2, 1] ], 'L') :- !.
tetromino([ [0, 0], [0, 1], [0, 2], [1, 0] ], 'L') :- !.
tetromino([ [0, 0], [1, 0], [2, 0], [2, 1] ], 'L') :- !.
tetromino([ [0, 2], [1, 0], [1, 1], [1, 2] ], 'L') :- !.
tetromino([ [0, 0], [1, 0], [2, 0], [3, 0] ], 'I') :- !.
tetromino([ [0, 0], [0, 1], [0, 2], [0, 3] ], 'I') :- !.
tetromino([ [0, 0], [1, 0], [1, 1], [2, 0] ], 'T') :- !.
tetromino([ [0, 0], [0, 1], [0, 2], [1, 1] ], 'T') :- !.
tetromino([ [0, 1], [1, 0], [1, 1], [2, 1] ], 'T') :- !.
tetromino([ [0, 1], [1, 0], [1, 1], [1, 2] ], 'T') :- !.
tetromino([ [0, 0], [0, 1], [1, 0], [1, 1] ], 'O') :- !.
tetromino([ [0, 0], [0, 1], [1, 1], [1, 2] ], 'S') :- !.
tetromino([ [0, 1], [0, 2], [1, 0], [1, 1] ], 'S') :- !.
tetromino([ [0, 1], [1, 0], [1, 1], [2, 0] ], 'S') :- !.
tetromino([ [0, 0], [1, 0], [1, 1], [2, 1] ], 'S') :- !.
tetromino(_, '-').

solve([]).
solve([S0|SS]) :- str2pos(S0, P0), sort(P0, P1), normalize(P1, P2), tetromino(P2, R2), writeln(R2), solve(SS).

result :- see('testpattern.txt'), read(SS), seen, solve(SS).