PrologのLogical Loopの解説

ECLiPSe CLPでソルバーを作るときに欠かせないLogical Loopの説明をしたいと思います。

Prologでプログラムを書いたことがない人は信じられないと思いますが、なんとPure Prologには繰り返し処理を書くための構文がなくて、ループごとに再帰処理を使った述語を定義して繰り返し処理を行います。

例えばLstというリストに入っている要素をすべて表示するという処理を書きたい場合、以下のようにdsp_lst/1という術語を定義して繰り返しを書いて行います：

main:-
	Lst=[a,b,c,d,e,f],
	dsp_lst(Lst).

dsp_lst([]).
dsp_lst([First|Rest]):-
	write(First),nl,
	dsp_lst(Rest).

実行結果：

?- main.
Yes (0.00s cpu)
a
b
c
d
e
f

このように繰り返しの為だけに定義した述語をauxiliary predicate（補助述語）と呼ぶようです。よくPrologのコードで出てくるのですが、述語名のうしろにアンダーバーとかを1つつけて、ループ用の補助述語を定義したりします。

上記かなり愚かしい仕様に思えますが、恐らく以下のような理由からだと推測します。
①Prologの述語は本来「動作」「処理」ではなく、引数同士の「関係」を記述するためのもの（関数ではなく述語と呼ぶゆえん。一階述語論理の述語）
②例えば以下のような述語があった場合、

pred(A,B,C):-
	term1(A,B,C),
	term2(A,C),
	term3(A,B).

term1～term3のそれぞれの引数同士の関係が「すべて」成り立つとき、pred(A,B,C)が真となる。本来カンマは「処理の区切り」ではなく「複数の述語どうしを結ぶ条件の&」を表すという原則がある（orは;もしくは同名の別の述語定義)。極論を言えばterm1からterm3の順番をバラバラにしても成り立つはず（実際は大いに記述の順番に依存しますが…理想とする姿がそこという意味）、単純に複数の述語を&で結んだものに過ぎないので繰り返しとかいう概念がそもそもない。

（余談ですが制約論理プログラミングの制約「のみ」で書かれた述語は述語内の制約の順番をバラバラに並び替えても基本的に問題なく動作します。Prologの理想に近い）

このような仕様に一石を投じたのがECLiPSe CLPのメイン開発者のJoachim Schimpfさんの書いた以下の論文です。
Logical Loops
この論文によってPrologに自然な形でのループ処理の記述方法が提示され、ECLiPSeやSicstus Prologなどで採用されています。

Logical Loopの書き方は、上記の補助述語でループを書いていた人に自然に受け入れられるような仕様となっています。逆にPrologで補助述語を使ったループを書いたことがない人は使いこなすまで時間がかかるかもしれません。再帰を使用してループを記述することに慣れている必要があります。

例えば上記のLstというリスト内の文字をすべて表示するプログラムをLogical Loopで書くと、以下のようになります。

main:-
	Lst=[a,b,c,d,e,f],
	(
		fromto(Lst,[First|Rest],Rest,[]) do
		(
			write(First),nl
		)
	).

上記のように
1.fromtoなどの繰り返し制御用の記述
2.do
3.(繰り返す処理)

の3つの部分を書きます。
補助述語との比較で理解すると良いのですが、
「1.fromtoなどの繰り返し制御用の記述」→述語の引数の部分
「3.繰り返す処理」→述語の内部の処理
となります。
補助述語の書き方をそのまま置き換えたような扱いなので、「繰り返す処理」の部分は別述語のように独立となっていて、ループの外で使われている変数などは明示的に指定しない限り一切使用することはできません。使いたい場合はparamという構文を使用して引数として渡す（後述）必要があります。

fromtoの4つの引数の意味は(First,In,Out,Last)となっていて、やはり補助述語と関連付けて理解すると良いのですが
In→補助述語の引数
Out→補助述語内で再帰呼び出しする際に指定する引数
Last→補助述語の引数がこの値でコールされたらループ終了
という感じです。
一番初めに補助述語をコールする際に指定する引数がFirstとなります。

駆け足になりますがfromto以外で使用できる構文を列挙していきます。これらを複数同時に指定することもできます。

foreach(X,List)
リストList内の要素が順にXに設定され処理が繰り返されます。リストを生成することもできます。Xはループ内局所変数です。

foreacharg(X,StructOrArray)
StructOrArrayの部分はECLiPseのArray（[](1,2,3,4)みたいな記述)や複合項 fukugoukou(1,2,3,4) を指定します。
最初の引数から順にXに設定され処理が繰り返されます。termを生成するためには使用できません。Xはループ内局所変数です。

foreacharg(X,StructOrArray,Idx)
引数が2個のものと同じ動きですがIdxに何番目の要素がXに入っているかの数字が入ります（arg(Idx,StructOrArray,X)がtrueとなる)。XとIdxはループ内局所変数です。

foreachelem(X,Array)
foreachargと同じ動きですが2次元配列などでも対応しますArray=[]([](1,2,3),[](4,5,6))などの場合Xに1,2,3,4,5,6が順に設定される。Xはループ内局所変数です。Arrayを生成するためには使用できません。

foreachelem(X,Array,Idx)
引数2個バージョンと同じ動きですがIdxにインデックス位置が設定されます。XとIdxはループ内局所変数です。

foreachindex(Idx,Array)
foreachelemと同じ動きですがXがなくIdxのみ設定されます。Idxはループ内局所変数です。

for(I,MinExpr,MaxExpr)
C言語などのfor(I=MinExpr;I<=MaxExpr;I++)と同じ動き。MaxExprは必ず値を設定しておく必要あり。Iはループ内局所変数です。 for(I,MinExpr,MaxExpr,Increment) 引数3個バージョンと同じ動きだがIncrementで何個づつIが増えるかを設定可能 multifor(List,MinList,MaxList) for/3と同じだがIに相当する変数をリストとして複数設定する。MinListとMaxListも対応する下限上限をリストで設定する。 Listはループ内局所変数 multifor(List,MinList,MaxList,IncrementList) 引数3つバージョンと同じだがIncrementListに増加分を設定できる count(I,Min,Max) forと同じのようだがMaxは値設定しなくてOK。ループ終了後にカウントした値など把握できる。 param(Var1,Var2,...) ループ内で使用したい変数を指定する。ここで指定しない限りループの外で使用している変数など使用できない。 補助述語に引数として渡すイメージ。 loop_name(Name) デバッグ用にループの名前を付けることができる。補助述語の名前のようなイメージ。他の述語と重複する名前は許されない。 最後に、先ほど「fromtoなどの記述は複数記述できる」と書いたのですが、これが面白くて、例えばリストを生成する用途で使用したりなどもできます。 リストList=[1,2,3,4,5]があったとして、ListSqにそれぞれの要素を2乗したリストを設定するようなプログラムを書いてみます。

main(LstSq):-
	Lst=[1,2,3,4,5],
	(
		fromto(Lst,[First|Rest],Rest,[]),fromto(LstSq,[FirstSq|RestSq],RestSq,[]) do
		(
			FirstSq is First*First
		)
	).

実行結果：

?- main(LstSq).
LstSq = [1, 4, 9, 16, 25]
Yes (0.00s cpu)

上記動作もfromtoの各引数に関して「補助述語に引数として渡している」イメージを持つと何が起こっているのかわかるのではないかと思います。

以下のような補助述語が生成されてると考えると良いと思います！

main(LstSq):-
	Lst=[1,2,3,4,5],
	auxiliary_predicate(Lst,LstSq).

auxiliary_predicate([],[]).
auxiliary_predicate([First|Rest],[FirstSq|RestSq]):-
	FirstSq is First*First,
	auxiliary_predicate(Rest,RestSq).