図 4.7: 不要なノード評価を始めないプログラム(seq.kl1)
ANDノードでは, 下につながる2つのノードのうち 一方のノードの評価結果がfならばもう一方のノードは評価する必要がない. またORノードでは, 一方がtならばもう一方のノードは評価する必要がない. このことを利用して不要なノード評価を行なわくしたのが 図4.7のプログラム(seq.kl1)である.
eval/2は, まずeval/2を呼んで左のノードの評価を行ない, and_node/3あるいはor_node/3を呼ぶ(5,6行目). and_node/3及びor_node/3は左のノードの評価結果によって, eval/2を呼んで右のノードを評価する(10,11行目), あるいは右のノードを評価を始めることなく評価値を返す(9,12行目).
seq.kl1の実行の様子を図4.8に示す. 不要なノード評価を始めないことにより 17ノード中9ノードについてのみeval/2が実行された.
このプログラムではnaive.kl1に比べて評価対象のノードが少なくてすむが (計算量が少なくてすむが)逐次にしか動かない. eval/2は2つのゴール(eval/2とand_node/3あるいはor_node/3)を フォークするが(5,6行目), フォークされた2つのゴールは並列には動かない. and_node/3及びor_node/3はeval/2の結果が求まるまで動けないからである.
