モチベーション
Prolog プログラミングにおいて、リスト処理は再帰処理として書くのが普通なのではないかと思います。
一方で、メタインタプリタ的なものを書く場合、述語定義 Head :- Body における Body 部分はリストではなくタプルです。
?- Goal = (foo :- bar1, bar2, bar3), Goal =.. [':-', Head, Body], Body =.. Body1.
Goal = (foo:-bar1, bar2, bar3),
Head = foo,
Body = (bar1, bar2, bar3),
Body1 = [',', bar1, (bar2, bar3)].
リストについて再帰処理を書く場合、
test_list([]) :- % リスト終端である
write(end_of_list), nl.
test_list([E | Rest]) :- % リスト終端でない
write(E), nl,
test_list(Rest).
のように書けますが、タプルについて再帰処理を書こうとすると、
test_tuple(E) :-
\+ E = (_, _), % 引数はタプルではない
write(E), nl,
write(end_of_tuple), nl.
test_tuple((E, Rest)) :- % 引数はタプル
write(E), nl,
test_tuple(Rest).
みたいになって、リストの場合に比べるとあまりすっきりと書けません。
リストの場合、 [a,b,c,d] は[a | [b | [c | [d | [] ]]]] なので終端に [] が出てくるのを待ち構えることができます。
| ?- X = [a | [b | [c | [d | [] ]]]].
X = [a,b,c,d]
yes
タプルの場合、(a,b,c,d) は (a, (b, (c, d))) なので終端にはこれが出てくれば終わりと言えるものがないうえに、最後の一要素（ここでは d）だけ他と違う扱いが必要です。
| ?- X = (a, (b, (c, d))).
X = (a,b,c,d)
yes
このため、タプルの再帰処理はリストの再帰処理に比べて以下のような欠点が出てしまいます:
-
','/2が出てこなければ最後の要素かな？という比較的あやふやな判断の仕方になってしまう - 最終要素についての処理だけ終端の判定部分に混ざってしまう
なので、タプルをトラバースする処理を書く場合、直接タプルについて再帰処理を書くよりも、タプルをリストに変換してリストの再帰処理を書く方が楽で間違えにくいのではないかと思いました。
実装
というわけで、タプルの再帰処理とリストの再帰処理両方を突き合わせることで、相互変換する述語を書いてみます。
%% tuple_list(?Tuple, ?List)
% タプル Tuple とリスト List を相互変換する。
tuple_list(A, [A]) :-
% タプルの場合、最後の要素 A 一つからなるタプル(?) は A そのもの。
% リストの場合、最後の要素 A 一つからなるリスト は [A]。
\+ A = (_,_), !.
tuple_list((A, Tuple), [A | List]) :-
% タプルの場合は、タプル Tuple の先頭に要素 A を追加したタプルは (A, Tuple)。
% リストの場合は、リスト List の先頭に要素 A を追加したリストは [A | List]。
tuple_list(Tuple, List), !.
実行例:
| ?- tuple_list((a,b,c,d,e), X).
X = [a,b,c,d,e]
yes
| ?- tuple_list(X, [a,b,c,d,e]).
X = (a,b,c,d,e)
yes
SWI-Prolog の場合、ライブラリとして提供されている comma_list/2 を使えば同じことができます。
comma_list/2 は、タプルとリストの相互変換に留まらず、タプル・リストの生成にも使えます:
?- comma_list((a,b,c,d), X).
X = [a, b, c, d].
?- comma_list(X, [a,b,c,d]).
X = (a, b, c, d).
?- comma_list(T, L).
L = [T] ;
T = (_A, _B),
L = [_A, _B] ;
T = (_A, _B, _C),
L = [_A, _B, _C] ;
T = (_A, _B, _C, _D),
L = [_A, _B, _C, _D] ;
:
（略）
しかし上に示した tuple_list/2 で同じことをすると無限ループに陥ってしまい、あっという間にメモリを使い果たしてしまいます。
個人的には、限られた状況で動けばそれでよいという了見でこれまで Prolog を触っていました。
しかし最近になって「The Power of Prolog」を読んで、論理的純粋性や多方向性を気にしなければいけない、と思い始めています。
タプル・リストの生成にも利用できる comma_list/2 の動作の方が望ましいのは明白です。
改善
SWI-Prolog のソースコード (library/prolog_code.pl) を見ると、comma_list/2 がどう実装されているかがわかります:
comma_list(CommaList, List) :-
phrase(binlist(CommaList, ','), List).
binlist(Term, Functor) -->
{ nonvar(Term) },
!,
( { Term =.. [Functor,A,B] }
-> binlist(A, Functor),
binlist(B, Functor)
; [Term]
).
binlist(Term, Functor) -->
[A],
( var_tail
-> ( { Term = A }
; { Term =.. [Functor,A,B] },
binlist(B,Functor)
)
; \+ [_]
-> {Term = A}
; binlist(B,Functor),
{Term =.. [Functor,A,B]}
).
var_tail(H, H) :-
var(H).
nonvar/1 や var/1 で条件分岐していることがわかりました。
タプルとリストの関係の定義を素直に書けば論理的に純粋に動作する Prolog コードが得られるに違いない、
と思っていたのですが、結構泥臭い条件分岐を書かなければならないのだなと思いました。
これを参考に tuple_list/2 に nonvar/1 や var/1 での条件分岐を追加して、以下の tuple_list2/2 を得ました:
%% tuple_list2(?Tuple, ?List)
% タプル Tuple とリスト List を相互変換する。
tuple_list2(T, L) :-
nonvar(T), !, % 第一引数（タプル）が与えられた場合
( T = (A, B) % 第一引数が ','/2 の場合、分解してリストに設定
-> L = [A | Lb],
tuple_list2(B, Lb)
; L = [T]). % 第一引数が ','/2 でない場合、最終要素
tuple_list2(T, [A | B]) :-
( var(B) % 第二引数の CDR が変数の場合
-> ( T = A, B = [] % CDR が [] のパターン
; T = (A, Tb), tuple_list2(Tb, B) ) % CDR が [] でないパターン
; B = [] -> T = A % 第二引数の CDR に [] が与えられた場合
; T = (A, Tb), % 第二引数の CDR が [] でない場合
tuple_list2(Tb, B) ).
なんとかそれらしく動くようになりました:
?- tuple_list2((a,b,c,d), X).
X = [a, b, c, d].
?- tuple_list2(X, [a,b,c,d]).
X = (a, b, c, d).
?- tuple_list2(X, Y).
Y = [X] ;
X = (_A, _B),
Y = [_A, _B] ;
X = (_A, _B, _C),
Y = [_A, _B, _C] ;
X = (_A, _B, _C, _D),
Y = [_A, _B, _C, _D] ;
:
（略）
当然ですが、GNU-Prolog でも同じように動作します。
まとめと感想
タプルとリストを相互変換する Prolog コードを書きました。
同機能を提供する SWI-Prolog の comma_list/2 を参考に、タプル・リストの生成にも使えるより汎用性の高い述語を得ることができました。
タプルとリストの関係の定義を素直に書けば、汎用的で論理的に純粋な動作をする Prolog コードが半ば自動的にできるに違いない、という幻想を抱いていたのですが、どうもそういうものではないようです。
かといって、あまりカット（! や ->）を多用して条件分岐を書いていくのも、非宣言的で Prolog プログラミングとしてはよろしくないのだろうという気がします。
私のように Prolog プログラミング教育を受けたことがない万年初心者だと、なにか述語を書こうとしたときに
- 自分の能力不足で手続き的プログラミングになってしまうのか
- ある程度経験のある人でも宣言的に書くことに限界があるのか
よくわからないのでそのへんのさじ加減というか常識がよくわからなくて難しいなと思いました。