節はある条件 (ガード) を満たすゴールを, ボディのゴールに書き換える書換
ルールであると見ることもできる. 図 1.1 に示すように
書き換えるべきゴールの集合
からひとつのゴールを取り出し, この書換えを施した結果をゴー
ルの集合に戻すのが実行の 1 ステップになる. 書換えを繰り返すことによっ
て最終的にはすべてのゴールが何もしないゴール `` true'' にまで書き
換えられると実行は終了する. この過程は, 最初に与
えられたゴールを `` true'' にまで書換えていく 簡約化
(reduction) であるとも考えられる.
この書換えはかならずしも逐次的にひとつずつ行なわなくとも良い. 複数の ゴールについて同時に行なえば, 実行は並列になる.
KL1 では複数のゴールが同じ 変数を共有することがある. あるゴール が変数の値を決めれば, それを共有する他のゴールは, その値を使ってどの節 を使って簡約化するかを決めることもできる. これが KL1 の通信機構である.
前掲のインバータのプログラムについて, メインプログラムを以下のように書 換えた場合を考えてみよう.
main :- not(1, X), not(X, Y), io:outstream([print(Y),nl]).
このように実行すると, X で示す変数は述語 not に関するふたつのゴールで 共有することになる.
KL1 では, 複数のゴールがあるときにはどの順番に実行するかは特に決めてお
らず, 処理系の都合で決めて良いことになっている.
仮に, まず最初の `` not(1,X)'' から先に実行するものとしてみよう. 第1引数は 1 だから, 第2引数 X の値は 0 に決まる. この X はもうひとつ のゴール `` not(X,Y)''の第1引数にもなっている. だからこのゴール の第1引数は 0 になったわけである. そこで, このゴールを実行すると Y は 1 に決まる. したがって, このゴール列の実行の結果, X は 0 に, Y は 1 になる.
実行の順序が変わったらどうなるだろう. 最初に二番目のゴール `` not(X,Y)'' を実行しようとしたとする. すると, 第1引数 X の値はまだ決 まっていないから, 述語 not のふたつの節のガードに書いてある適用条件 In=0 と In=1 は, どちらも In の値がまだ決まっていないこと になる. これではどの節を使って良いのか, 条件を試すことができない. こ のような場合, 当面の間このゴールの実行は見合わせる. これを実行の 中断 (suspension) と呼ぶ.
このゴールがすぐ実行できないとなると, 他にはもうひとつのゴールしかする ことはない. そこでそのゴールを先に実行すると X の値が 0 に決まる. こ れで先程実行を中断していたゴールの第1引数の値は決まり, 実行を中断し続 ける理由はなくなった. そこで, このゴールの実行を再開する. こんどはガー ドの真偽を調べるのに障害はなく, 無事 In=0 の節が選ばれ, Y の値は 1 に決まる. これだけが KL1 の通信と同期の機構で, これ以外には何もない.
要約すると以下のようになる.
