このプログラムでは変数 List がふたつのプロセスから共有されており, naturals が作ったリストを sum に渡す手段になっている.sum_up_to(N,Sum) :- naturals(N,List), sum(List,Sum).
このふたつのプロセスは同じボディの中に書かれているのだから, どんな順序 で実行しても良い. 2引数の述語 sum はガードの条件がないから, List の値 が決まっていなくても実行でき, 3引数の方の述語 sum を呼び出す. こちら の方は引数の値によってどの節を選ぶか決めなければならないので, 値が決ま るまで待たされるわけである.
さて, ここで先ほどの自然数のリストを作る述語の定義をもう一度見てみよう.
前にも書いたように, ふたつ目の節のボディのユニフィケーション, 足し算, 再帰呼び出しの三者はどんな順でも実行できる. ユニフィケーションが他の ゴールと並列に実行できるということは, まだ計算が終らないのに答を返せる ということである. もちろん答は全部求まったわけではなく, 結果を返す引 数とユニフィケーションしているコンス構造の cdr である Rest は, 再帰呼び出しゴールの実行結果が入るまでは変数のままだから, 前述の未完成 データ構造である. しかし, 計算結果が全体としてはコンスであることはこ のユニフィケーションで既に決まってしまっている. また, その car, つま りリストとして見たときの最初の要素は, 最初の呼び出しの第1引数が 0 なの だから, もうそれに決まっている.naturals(N,M,List) :- N>=M | List=[]. naturals(N,M,List) :- N<M | List=[N|Rest], N1:=N+1, naturals(N1,M,Rest).
今度は総和を求める方のプロセスの本体である3引数の sum の方を, もう一度 振り返ってみよう.
述語 naturals の結果がコンスであることまでもう決まっているのだから, ガー ドの条件 (実際にはヘッド中に略記されている) の判定はでき, ふたつめの節 を選べる. そしてその car (ここでは変数 One で受けている) が 0 である ことも決まっている. 第2引数の PSum は最初は 0 にして呼んでいるのだか ら, もう足し算の引数はふたつとも決まっているわけである. だから 0+0 という足し算は, naturals の実行が少し進んだだけでもうすぐにでも実行で きるようになっているわけだ.sum_up_to(N,Sum) :- naturals(N,List), sum(List,Sum).
再帰呼び出しの方はそうはいかない. まだ naturals が最初の1段階しか進ん でいないとすると Rest の値は決まっていない. つまり, 再帰的に呼び出さ れた sum では第一引数がまだ決まっていないわけで, どの節を選べば良いか の判定ができない. この Rest は naturals と sum のふたつのプロセスの間 で共有する変数になっていて, naturals がその値を決めることになる. だか ら sum の再帰呼び出しの実行は naturals の方の計算がもっと進むまで待た される. この後に naturals の方がもう一段進めば, sum の方ももう一段進 めるようになる.
このように, 要素がまだ決まっていない構造体を結果として返し, 後
からその要素を確定していくことができる, という仕組は, KL1 の大きな特徴
のひとつである. 要素がすべて決まるまで結果を返せないのだとしたら,
naturals の実行がすべて終るまで sum の実行を始めることができない. そ
れだけ並列度が低くなってしまうわけである.