非決定性計算はストリーム処理のように, 「生成してテストする」応用に有用である. 正の整数の二つのリストがあるとし, 一方は第一のリストから, 他方は第二のリストからとった一対の整数で, 和が素数になるものを見つける問題を考える. 有限の並びの演算でこれをどう扱うかは2.2.3節で, 無限のストリームについては3.5.3節で見た. その解決法はすべての可能な対の並びを生成し, その和が素数になる対を選ぶため, フィルタすることであった. 2章のように, まずすべての対の並びを実際に生成するか, 3章のように生成とフィルタを差し込むかは, 計算をどう構成するかの本質的な姿には関係しない.
非決定性の解決法は, 違った姿を惹き起す. 第一のリストから一つの数を, 第二のリストからもう一つの数を(何らかの方法で)選び, その和が素数であるように(何らかの機構を使って)要求したと考えよう. これは次の手続きで表せる:
(define (prime-sum-pair list1 list2)
(let ((a (an-element-of list1))
(b (an-element-of list2)))
(require (prime? (+ a b)))
(list a b)))
この手続きは, その解法を規定するよりは, 単に問題を述べ直しているように見えるかも知れない. しかしこれは正真正銘の非決定性プログラムである.42
鍵になる考えは非決定性言語での式は一つ以上の可能な値を持ち得るということである. 例えばan-element-ofは与えられたリストの任意の要素を返すであろう. われわれの非決定性プログラム評価器は, 可能な値を自動的に選び, その選択を覚えていることで働く. 後続の要求が満されなければ, 評価が成功するまで, あるいは選び切るまで, 評価器は新しい選択を試み続ける. 遅延評価器が, 値をどう遅延させ, 強制するかの細部からプログラマを解放したように, 非決定性プログラムの評価器は, どう選択するかの細部からプログラマを解放する.
非決定性評価とストリーム処理で惹き起される時間の異る姿を対照させることは有用である. ストリーム処理は, 可能性ある解答のストリームが集められる時と, 実際のストリーム要求が作り出される時を切り離すのに遅延評価を使う. 評価器は, 可能な答のすべては無時間の並びとしてわれわれの前に存在するという幻影を作る. 非決定性評価では, 式は一連の選択で決められる, 可能な世界の集合の探索を表す. 可能な世界の中には, 行き止りのものもあるが, 残りは有用な値を持つ. 非決定性プログラムの評価器は, 時は分岐し, プログラムは異る可能な実行履歴を持つという幻影を作る. 行き止りにたどり着くと, 直前の選択点を再訪し, 別の分岐へ進む.
次に実装する非決定性プログラムの評価器は, ambという新しい特殊形式に基づくため, amb評価器という. amb評価器の駆動ループに上のprime-sum-pairの定義を(prime?, an-element-ofおよびrequireの定義と共に)入力し, 手続きを次のように走らせることが出来る:
;;; Amb-Eval input: (prime-sum-pair '(1 3 5 8) '(20 35 110)) ;;; Starting a new problem ;;; Amb-Eval value: (3 20)返された値は評価器がリストのそれぞれから要素を繰り返し選び, 成功した選択が出来てから得られる.
4.3.1節はambを紹介し, 評価器の自動探索機構によって, それが非決定性をどう支援するかを説明する. 4.3.2節は非決定性プログラムの例を示し,
4.3.3節は通常のScheme評価器を修正してamb評価器を実装する方法の細部を述べる.
42
数が素数かどうかテストする手続きprime?はすでに定義したと仮定する. prime?は定義してあっても, prime-sum-pair手続きは, 1.1.7節の初めにあった「Lispもどき」による役立たずの平方根関数定義のように怪しげにみえる. 事実平方根手続きは, 非決定性プログラムとして実際にこの書き方で形式化出来る. 探索機構を評価器に組み込むことで,
真に宣言的記述と, 答をいかに計算するかの命令的仕様の間の区別を壊しつつある. 4.4節においてこの方向へ更に進むことになる.