図 4.9: 不要なノード評価を打ち切るプログラム(cont.kl1)
seq.kl1では不要なノード評価を行なわないことを
まず一方のノードを評価し, その結果によってはもう一方の評価を始めない.という逐次的な方式で実現したが, ここでは
両方のノードとも評価を始め, たまたま先に求まった一方の評価結果によっては, もう一方の評価を途中で打ち切る.という並列実行が可能な方式で実現する. この方式では各ノードが並列に評価されうるわけである. プログラム(cont.kl1)を図4.9に示す.
eval/3は, 下のノードを評価する2つのeval/3と,
それらを制御するand_node/6あるいはor_node/6をフォークする(7
12行目).
フォークされた2つのeval/3は並列に実行されうる.
eval/3, and_node/6, or_node/6 の第1引数は ノードの評価を途中で打ち切るための引数である. この引数を以下では『打ち切り引数』と呼ぶことにする. 3つの述語とも打ち切り引数をチェックする節(5及び15,20行目)の優先度が alternativelyによって高くなっている. このため打ち切り引数がabortに具体化されていたならば, 他の引数の具体化状況に依らず打ち切り引数をチェックする節が選択され ノードの評価は行なわれない.
and_node/6は, 一方のノードの評価結果がfであることがわかった段階で評価値Eをfに決定し, 打ち切り引数をabortに具体化してもう一方のノードの評価を打ち切る(18,19行目). or_node/6は, 一方の評価結果がtであることがわかった段階で同様の処理を行なう(23,24行目). 打ち切り引数の具体化は, and_nodeあるいはor_nodeからevalへ, そしてand_nodeあるいはor_nodeを経由してさらに下のevalへと 伝播して行き(図4.10参照), ノードの評価が打ち切られる.
図 4.12: ゴールの順序を入れ換えたcont.kl1の実行
cont.kl1の実行の様子を図4.11に示す. 2つのノードが評価を打ち切られ(図(a) 9,11行目, 図(b) abort), 17ノード中9ノードについてのみeval/3の通常実行が行なわれた. 図4.11を図4.8と比較すると seq.kl1と同じノードが同じ順序で評価されたことがわかる. しかしこれは「たまたまそのように評価された」だけである. seq.kl1は評価順序を「まず左のノードを評価し, 次に右へ行く」と決めていたが, cont.kl1は「どちらもいつでも評価を試みてよい」プログラムであり, 評価順序は定めていない.
前述したようにこのプログラムは並列実行が可能である. 即ち, ある時刻において実行可能なゴールが一般に複数存在する. 一方このプログラムではゴールに対して優先度を指定していないので すべてのゴールは同じ優先度をもち実行可能なゴールはどれでも実行されうる. これは言い換えると 「あるゴールが実行可能であっても, 一般に, 同じ優先度をもつ実行可能なゴールが 他にも存在するので, そのゴールが実行される保証はない」 ということである.
評価の打ち切りを効率よく行なうには, 評価する必要のないノードに対応するeval/3の実行が始まる前に and_node/6及びor_node/6の実行が開始されなければならない. 実行の終わったeval/3の打ち切り引数を具体化しても意味がないからである. しかし, 上述したように, そのように実行される保証はない. 最悪の場合はすべてのノードについてeval/3の実行が終了してから and_node/6及びor_node/6が実行されノード評価の打ち切りは全く行なわれない.
図4.9のcont.kl1では, ボディの左側のゴールが右側より先に実行が試みられたので, and_node/6及びor_node/6がeval/3よりも先に実行され ノード評価の打ち切りが行なわれた. これは「たまたま期待通りに実行された」と考えるべきである. ひとつのボディ内の優先度を指定していないゴール群はすべて同じ優先度を持つので, 何らかの都合によりeval/3がand_node/6あるいはor_node/6より先に実行されても 文句は言えない.
cont.kl1の8行目と9行目, 及び11行目と12行目を入れ換えると and_node/6及びor_node/6の実行はeval/3の後になる. この時のeval/3の実行の様子を図4.12に示す. 図からわかるようにノード評価の打ち切りは全く行なわれない. 17ノードすべてについてeval/3が実行されてしまった.
