Prologを嗜む。 では、おれが今、論理プログラミング言語Prologを勉強していて、 有名な演習問題集であるP-99を解いていることを話した。

同時に、Prologへの入門（I. Bratko） という古典的な名著も古本で購入し、読み進めている。 おれはすっかりPrologに嵌っている。 Prologを書けない知的障害者は屠殺すべきだと、最近では真剣にそう考えている。

P-99は日に一問程度の嗜みペースで進めていき、ついに一章リスト操作を卒業手前まで来た。 P27はこんな問題だ。

P27. 与えられたリストをグループにする方法をバックトラッキングにより全列挙せよ。 ただし、各グループの大きさは与えられるものとする。

• (a) group3(Xs, G1, G2, G3)を実装せよ。Xsの大きさは9、G1,G2,G3の大きさは2,3,4とする。（例: group3([aldo,beat,carla,david,evi,flip,gary,hugo,ida],G1,G2,G3).）
• (b) (a)を一般化し、group(Xs, Ns, Gs)を実装せよ。Xsの大きさはNsの和とする。（例：group([aldo,beat,carla,david,evi,flip,gary,hugo,ida],[2,2,5],Gs).）

論理プログラミングのポイントは、再帰的な構造を見出すことだ。 (a)を例にして議論すると、今、残りのスロットが[x,y,z]である時、 残りメンバーのヘッドをxに入れれば残りのスロットは[x-1,y,z]になり・・・ という再帰的な構造を見出すことが出来る。

この論理を愚直に実装したおれのgroup3はこうなった。 実際、(a)についてはこれで解けた。

1
2
3
4

group3([], [], [], []).
group3([X|Xs], [X|G1], G2, G3) :- group3(Xs, G1, G2, G3), length(G1, Len), Len < 2.
group3([X|Xs], G1, [X|G2], G3) :- group3(Xs, G1, G2, G3), length(G2, Len), Len < 3.
group3([X|Xs], G1, G2, [X|G3]) :- group3(Xs, G1, G2, G3), length(G3, Len), Len < 4.

問題は(b)だ。 方針自体は簡単で、 ヘッドの要素について、 それを先頭の集合に入れるか、その他の集合に入れるかの ふたつの世界線に分岐出来ればよい。 そうすれば、あとはPrologが自動的に全探索をしてくれる。

しかし、これがいくらやっても書けなかった。 かつて競プロで味わったのと同じような絶望 （参考： 競技プログラミングは残酷な地頭ゲー ） を数日味わったあと、知的障害者のおれは泣きながら投了し、解答を見た。 以下が(a)に対する模範解答になる。この形からならば、(b)を書くのは簡単なので省略する。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

group3(G,G1,G2,G3) :- 
   selectN(2,G,G1),
   subtract(G,G1,R1),
   selectN(3,R1,G2),
   subtract(R1,G2,R2),
   selectN(4,R2,G3),
   subtract(R2,G3,[]).

selectN(0,_,[]) :- !.
selectN(N,L,[X|S]) :- N > 0, 
   el(X,L,R), 
   N1 is N-1,
   selectN(N1,R,S).

el(X,[X|L],L).
el(X,[_|L],R) :- el(X,L,R).

何を言ってるかわかるだろうか？ group3は、自然言語でストレートに書いたらこうなるだろうという形だ。 問題はselectN、とりわけelだ。

selectNのやりたいこと自体は自明だ。 「LからN個選択した集合はSである」。 Prologによってそんなパターンが全探索される。

問題はその中身だ。 再帰部分は良いとして、一体elというのは何をしているんだ？ 実験してみるとよくわかる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

?- el(2,[1,2,3,1,2,3],X).
X = [3, 1, 2, 3] ;
X = [3] ;
false.

?- el(X,[1,2,3,1,2,3],L).
X = 1,
L = [2, 3, 1, 2, 3] ;
X = 2,
L = [3, 1, 2, 3] ;
X = 3,
L = [1, 2, 3] ;
X = 1,
L = [2, 3] ;
X = 2,
L = [3] ;
X = 3,
L = [] ;
false.

selectNの中でこのelという関数は、 「Sの中に、あるXを含めるか含めないか」という世界線の分岐を表現していることになる。 欲しかった論理がこんな小さくて汎用的な実装によって表現されて、 それを組み合わせることでより複雑な問題を解けてしまっていることにPrologの美しさを感じる。 これは、論理の合成なのだ。

反省のため、どうすればこの発想に至れたか考えてみよう。

まずおれは、Xをとるかとらないかの２つの世界に分岐させることが出来ればよいという発想にはたどり着いていた。 しかしこの考えは、「先頭のXをG1か、そうでなければG1以降のどこかに入れる」という 入れ先の分岐を目指しているため、この時点で詰んでいるかはともかく、 Prolog的には筋は悪い。なぜかというと、データの更新について考えているからである。 Prologはこのような低俗な考えを受け付けないことが多い。

そうではなくまず素直に、selectNとsubtractによる実装を考えればよかった。 そうすれば、el(X,L,R)にダイレクトにたどり着けた可能性が十分にある。 なぜならば、これは「Lを順に見ていった結果、あるXを採用したとすると、残りの探索領域はRである」 という意味だからである。 このように、リストをデータではなく探索空間として見ることがPrologにとって受け入れられることは多い。

ポインタではなく、データとインデックスでもなく、イテレーションでもなく、探索空間と見る。 そして、それは何か具体的な値ではなく、ただのパターンであると見る。 こういった数学的、抽象的な考え方が出来なければPrologを書くことは難しい。 恐ろしく難易度の高い言語だ。Prologをネイティブに書ける人間は尊敬出来る。

屠殺されたくなかったらPrologをやるしかない。