Ex. 4.67
規則の適用 → 規則の適用 → 規則の適用 → ...
というループである。実際の関数の再帰は、
qeval → simple-query → apply-rules → apply-a-rule → qeval → ...
である。規則のユニファイや規則の本体を呼び出し実行しているのは、apply-a-rule なので、ここで履歴を検査してループ検知、および、履歴の記録をすればよい。
規則を実行する際、今実行しているのが、前回実行した規則と同じだったらループしていると分かる。
ループを発見したときの対処はユニファイ失敗と同じでよい。
履歴は大域環境に保存することにする。つまりグローバル変数とする。 (履歴を引数でたらいまわし、、、は面倒だったので諦めた。)
なお、単純ループのみ対象とする。規則→別の規則→元の規則というようなややこしいループは対象としない。なので履歴には前回実行した規則だけ保存すればよい。
こんな感じ
(define history 'dummy) ;; グローバル変数に履歴を追加
(define (query-driver-loop)
(set! history 'dummy) ;; 履歴を初期化
(prompt-for-input input-prompt)
...(ry
(define (apply-a-rule rule query-pattern query-frame)
(let ((clean-rule (rename-variables-in rule)))
(let ((unify-result
(unify-match query-pattern
(conclusion clean-rule)
query-frame)))
(if (eq? unify-result 'failed)
the-empty-stream
(if (eq? history (conclusion rule)) ;; 履歴チェック
the-empty-stream ;; ループを検知したら終了
(begin (set! history (conclusion rule)) ;; 履歴に今実行している規則をセット
(qeval (rule-body clean-rule)
(singleton-stream unify-result))))))))
太字が追加変更分。
履歴のチェックはユニファイのあとにおくこと。
ユニファイの前におくと、ユニファイしないルールまで履歴の対象になりまずい。(DBからルール探してるだけなのに履歴に残る）
動作はこんな感じ
;;; Query input: (outranked-by2 (Bitdiddle Ben) ?who) ;;; Query results: (outranked-by2 (Bitdiddle Ben) (Warbucks Oliver))
outranked-by2 は、Ex. 4.64 で無限ループしていたバージョンだが、ループ検知のおかげで、1回だけ実行して止まっている。