モード解析[2]を行ない, 各データを生成するゴールが判明すれ ば, 単純な要求駆動型実行は可能である. しかし, 図 1 の ように実行中断が多発するため, なんらかの基準で データの必要度を解 析し, すぐに必要な計算は遅延しない必要がある. KL1 ではガード単一化と 組み込み述語の実行のときに変数の具体値が必要になる. 従って, 抽象実行 などによって, ゴールが生成するデータの消費ゴールを追跡し, その必要度を 解析すると, どのゴールを遅延するのが良いのか判定できると考えられる (図 3). しかし, 次のような簡単な例でも, その解析は困難であ る.
1: main(L,R) :- foo(L,0,R). 2: foo([], C0,C) :- C=C0. 3: foo([N|L],C0,C) :- bar(N,C0,C1), foo(L,C1,C).foo/3 は再帰的にリスト L に対し bar/3 の処理を行うが, bar/3 の生 成データを参照しなくても foo/3 は実行を終了できるので, bar/3 は要求駆 動で実行する方が良いと判断できる. しかし, bar/3 の処理が簡単に終わる ような場合は実行時間・消費メモリとも数十倍以上大きくなってしまう. 従っ て, 極端に性能が低下することを防ぐためには, この例では bar/3 は遅延し ない方が良い (図 4).
|
・生成するデータが他のゴールの入力引数になっている場合は, そのゴールは遅延しない ・生成するデータが構造体の内部に格納される場合は, 要求駆動ゴール候補にする ・あるゴールが要求駆動で実行される場合は, その子ゴールも実質的に要求駆動になっているので, 要求駆動ゴール候補の子ゴールは自己再帰を除いて, 遅延評価しない |
