簡単なプログラム実行

まず次のプログラムの実行に関して, リダクションを試みる順番を考える.

main :- true | q, r.
q :- true | s, t.
r :- true | true.
s :- true | true.
t :- true | true.

あるゴールがリダクションし, そこで生成されたサブゴールが左優先で リダクションが試みられると仮定する. ゴール呼び出しが入れ子になっている場合, ゴールリダクションによって 生成されたサブゴールが LIFO で リダクションが試みられるとすると図 4.1 の順に実行されるであろう .

  
図 4.1: リダクション順の例

非決定性がないこのようなサスペンドしない実行が, 最も効率良いものと言える . しかしデータ処理が絡んでくるとそうとも言えない場合がある. 生産者-消費者 の問題を使って次項で説明しよう.