プログラミング言語を使うことで，膨大な量の詳細に飲み込まれないで済んでいる． Lispがよいプログラミング言語なのは，それ自身が多くの詳細を扱ってくれて， プログラマが耐えられる複雑さの限界を有効に使わせてくれている． この章ではマクロでLispにさらに別の種類の詳細を扱わせる方法を示す． 非決定的なアルゴリズムを決定的なものに変換することの詳細だ．
この章は5つの部分に分けられる． まず，非決定性とは何かを説明する． 次に，非決定的なchooseとfailを継続を使ってSchemeで実装する． 3番目では，第20章の継続渡しマクロを基礎にCommon Lispで実装したchooseとfailを示す． 4番目では，オペレータcutをPrologとは独立に理解する方法を示す． 最後に，非決定的オペレータの改良について考察する．
この章で定義される非決定的な選択オペレータは， 第23章のATNコンパイラと第24章の埋め込みPrologを実装するのに使われる．
非決定的アルゴリズムはある意味では超自然的な予見に基づいて動作するものだ． 超能力を持ったコンピュータに触れることのない私達に，どうしてそんなものが必要なのだろうか？\ それは非決定的アルゴリズムを決定的アルゴリズムでシミュレートできるからだ． 純粋に関数的なプログラム ---すなわち副作用の一切ないもの--- では， 非決定性は特に直截的になる． 純粋に関数的なプログラムでは非決定性はバックトラックを用いた探索で実現できる．
この章では，関数的なプログラムにおいて非決定性をシミュレートする方法を示す． 非決定性のシミュレータがあれば， 非決定的なコンピュータが出すはずの答えを得ることが期待できる． 多くの場合，超自然的な予見に頼ったプログラムを書く方がそうでないプログラムを書くより簡単だ． よって非決定性のシミュレータがあるとうれしい．
この節では非決定性によって得られる力のクラスを定義する． 次の節ではサンプルにおいてそれらの利用を試してみる． これらの章の例はSchemeで書かれている． （SchemeとCommon Lispのいくらかの相異点はlxjページにまとめてある）
非決定的アルゴリズムが決定的アルゴリズムと違うのは， 2つの特殊なオペレータchooseとfailが使える点だ． chooseは有限集合を引数に取ってその要素を1つ返す関数だ． chooseがどのように「選択する」かを説明するには， まず「未来の計算」という概念を導入する必要がある．
ここではchooseを，リストを引数に取ってその要素を1つ返す関数chooseとして表現する．
各要素について，それが選ばれた場合に計算が進み得る未来の集合が存在する．
次の式では，
(let ((x (choose '(1 2 3))))
(if (odd? x)
(+ x 1)
x))
計算がchooseに行き着いたとき，3つの未来があり得る．
chooseが1を返す場合，計算はifのthen節へ進み，
返り値は2になる．
chooseが2を返す場合，計算はifのelse節へ進み，
返り値は2になる．
chooseが3を返す場合，計算はifのthen節へ進み，
返り値は4になる．
この場合，chooseの返り値が分かれば即座に，未来の計算がどうなるか正確に分かる．
一般の場合では，各選択肢は可能な未来の集合と関連づけられている．
未来の中にはさらにchooseを使うものがあり得るからだ．
例えば次の式では，
(let ((x (choose '(2 3))))
(if (odd? x)
(choose '(a b))
x))
1つ目のchooseの時点で，2つの未来の集合がある．
chooseが2を返す場合，計算はifのelse節へ進み，
返り値は2になる．
chooseが3を返す場合，計算はifのthen節へ進む．
この時点で，計算の道筋は2つの可能性に分岐する．
aが返されるものと，bが返されるものだ．
第1の集合には1つの未来が，第2の集合には2つの未来が含まれるので， 計算には合わせて3つの未来があることになる．
重要なのは，chooseに複数の選択肢が与えられた場合，
各選択肢に可能な未来の集合が関連づけられているという点だ．
そのうちどれを返すべきだろうか？
chooseの動作は，次のようになると思ってよい．
failの呼び出しを含まない未来に進み得るもののみ．
chooseはfailと等価．
例えば次の式では，
(let ((x (choose '(1 2))))
(if (odd? x)
(fail)
x))
各選択肢には未来が1つずつある．
1を選んだ場合の未来にはfailの呼び出しが含まれるので，2のみが選ばれる．
よって上の式全体は決定的だ．
つまり，必ず2を返す．
しかし，次の式は決定的ではない．
(let ((x (choose '(1 2))))
(if (odd? x)
(let ((y (choose '(a b))))
(if (eq? y 'a)
(fail)
y))
x))
1つ目のchooseにおいて，
1を選んだ場合には2つの可能な未来があり，2を選ぶと1つの可能な未来がある．
しかし1を選ぶと，未来は実は決定的だ．
aを選ぶとfailの呼び出しにつながってしまうからだ．
よって式全体の返り値はbまたは2になり得る．
最後に，次の式の返り値は1つしかあり得ない．
(let ((x (choose '(1 2))))
(if (odd? x)
(choose '())
x))
なぜなら，1が選ばれた場合，未来は選択肢のないchooseに行き着くからだ．
つまりこの例は2つ前のものと等価だ．
ここまでの例からはまだ明らかにならないかもしれないが， たまげる程強力な抽象化手法が手に入ったのだ． 非決定的アルゴリズムでは 「後でどうなってもfailの呼び出しに行き着かないような要素を選べ」と言うことができる． 例えば，次のコードは完全に正しい非決定的アルゴリズムで， Igorという名前の人が先祖にいるかどうかを調べる．
Function Ig(n)
if name(n) = `Igor'
then return n
else if parents(n)
then return Ig(choose(parents(n)))
else fail
オペレータfailはchooseの返り値に影響を与えるために使われている．
failに出会うことがあれば，chooseの選んだ選択肢は誤っていたということだ．
定義からchooseは適切な選択肢を選ぶので，
計算処理がある経路に進まないようにしたいときは，
その経路のどこかにfailを置けば，その経路に計算が進むことはない．
よって関数Igは祖先の世代を再帰的に辿る過程において，
分岐点それぞれにおいて父方を選ぶか母方を選ぶか決定し，Igor氏につながる経路を選ぶことができる．
それはあたかもプログラムが， chooseに選択肢の中から何らかの要素を選ばせ，その返り値を必要とする限り何かに使い， そしてその後，chooseがどれを選んでいたらよかったかを，failを拒否の基準として， 遡って決定できるようなものだ． すると，そう，それがまさにchooseの返した値だと分かる． よってモデルとしてはchooseに予知能力があることになる．
実際にはchooseに超自然的な力はない． chooseのどの実装も，推定が誤っていたときにはバックトラックを行うことで， 適切な推定をシミュレートしなければならない． ちょうどネズミが迷路の出口を探すようなものだ． しかしバックトラックは完全に裏で行うことができる． 何らかのchooseとfailが手に入れば， どちらの親をたどるべきかの推定が本当に可能かのように，上のようなアルゴリズムが書ける． chooseを使うと，問題空間を探索するアルゴリズムを書くだけで， 問題空間内で答えを探すアルゴリズムが書ける．
(define (descent n1 n2)
(if (eq? n1 n2)
(list n2)
(let ((p (try-paths (kids n1) n2)))
(if p (cons n1 p) #f))))
(define (try-paths ns n2)
(if (null? ns)
#f
(or (descent (car ns) n2)
(try-paths (cdr ns) n2))))
\caption{決定的なツリーによる検索．}
\label{fig:DeterministicTreeSearch}
(define (descent n1 n2)
(cond ((eq? n1 n2) (list n2))
((null? (kids n1)) (fail))
(else (cons n1 (descent (choose (kids n1)) n2)))))
\caption{非決定的なツリーによる検索．}
\label{fig:NoneterministicTreeSearch}
古典的問題の多くは探索問題として定式化できるが，
そのような問題ではしばしば非決定性が便利な抽象化手法だと分かる．
nodesはツリーのノードのリストに束縛されており，
(kids n)はノードnの子孫を返すか，または子孫がないなら#fを返す関数だとしよう．
欲しい関数(descent n1 n2)は，ノードn2がノードn1の子孫のとき，
n1からn2までの経路上のノードのリストを返すものだ．
\reffig{fig:DeterministicTreeSearch}には非決定性を使わない実装を示した．
非決定性を使うと経路を発見する際の詳細を忘れていられる．
「目的とする節点につながる経路があるようなノードnを見つけろ」
とchooseに単に命ずるだけでよい．
非決定性を使うと\reffig{fig:NoneterministicTreeSearch}のようにdescentをもっと簡潔に描ける．
\reffig{fig:NoneterministicTreeSearch}の方では適切な経路上のノードを明示的に探してはいない．
chooseが望ましい性質を持つ節点nを選んだという仮定に基づいて書かれている．
決定的なプログラムに見慣れていると，
chooseは，どのnならば引き続く計算処理が失敗しないか推定できるかのように
機能しなければならないことに気付かないかもしれない．
(define (two-numbers)
(list (choose '(0 1 2 3 4 5))
(choose '(0 1 2 3 4 5))))
(define (parlor-trick sum)
(let ((nums (two-numbers)))
(if (= (apply + nums) sum)
`(the sum of ,@nums)
(fail))))
\caption{サブルーチン内のchoice．}
\label{fig:ChoiceInSubroutine}
きっとchooseの威力が一層際立つ例は
呼出側の関数においてすらどのようなことが起きるか推測できる能力だろう．
\reffig{fig:ChoiceInSubroutine}には，
和が呼出側の関数の与えた数になるような2つの数を推定する関数の組を示した．
最初の関数two-numbersは非決定的に2つの数を選び，それらをリストに入れて返す．
parlor-trickを呼び出したとき，
中ではtwo-numbersが呼ばれて2つの整数のリストが得られる．
選択をするとき，two-numbersはユーザの入力した整数にアクセスできないことに注意しよう．
chooseの推定した2つの整数の和がユーザの入力と等しくない場合，処理は失敗する．
chooseは失敗に終わる処理経路を避けることを利用してよい．
よって呼出側が適切な範囲の数を与えたときは，chooseは正しい選択をするものと仮定してよい
（実際もそうなる）
\footnote{Common Lispでは引数の評価順が左から右となっているのに対し，
Schemeでは定められていないため，
この呼び出しからは(THE SUM OF 5 2)が返されるかもしれない．}．
> (parlor-trick 7) (THE SUM OF 2 5)
単純な探索ではCommon Lispの組込み関数find-ifでも十分かもしれない．
非決定的な探索の利点はどこにあるのだろう？
選択肢のリストを，望ましい性質の要素を求めて頭から順に調べるのではいけないのだろうか？
chooseと古典的な反復との決定的な違いは，失敗について無限のエクステントを持っていることだ．
非決定的なchooseは，任意の長さの未来を見通せる．
chooseの選んだ選択肢が将来のいずれかの時点で失敗に終わるときは，
chooseはその選択肢を避けると思っていてよい．
parlor-trickで見たように，
オペレータfailは，制御がchooseを呼んだ関数から戻った後ですら機能する．
この類の探索失敗は，例えばPrologの行う探索でも見られる． 非決定性がPrologで便利なのは，その中心機能の一つがクエリに一つずつ答える能力だからだ． Prologは，条件を満たす答えを全て一度に返すのではなくこのような道筋を辿ることで， 下手をすると無限に大きい解集合を吐きかねない再帰的な規則を扱うことができる．
descentに対する第一印象はマージソートに対するものと似ているかもしれない．
処理はどのように行われるのだろう？
マージソートと同様，処理は暗黙のうちに行われるが，しかし確かに行われる．
第22章3節では，
これまで示したコード例がいずれも実際のプロセスとして走るようなchooseの実装を解説する．
これらの例は抽象化技法としての非決定性の価値を示した． プログラミング言語の最高の抽象化は，キータイプ量だけでなく思考を節約させてくれる． オートマトン理論では非決定性を使わないと想像すら難しい証明もある． 非決定性の使えるプログラミング言語はプログラマに同様の利点を与えてくれる．
この節では継続を使って非決定性をシミュレートする方法を示す．
\reffig{fig:ChoseFailInScheme}にはchooseとfailのSchemeによる実装を示した．
chooseとfailは，裏側ではバックトラックによって非決定性をシミュレートする．
バックトラックを使う探索プログラムは，
どうにかして，選択肢が失敗に終わった場合に別の選択肢を辿るための十分な情報を保存しなければならない．
その情報は継続の形でグローバルなリスト*paths*に保存される．
関数chooseには取り得る選択肢のリストが渡される．
選択肢が空の場合はchooseはfailを呼ぶが，これは計算を一つ前のchooseまで戻す．
選択肢が(first . rest)の形をしていれば，
chooseはまず*paths*に
chooseがrestに対して呼ばれるような継続をプッシュし，
次にfirstを返す．
関数failの方が単純で，*paths*から継続をポップして呼び出すだけだ．
*paths*が空リストのときはfailはシンボル@を返す．
しかしfailは，普通の関数が値を返すように@を返すことはしない．
それでは@は一番近くのchooseの返り値になってしまう．
本当に望ましいのは@をトップレベルに返すことだ．
このためにccをfailが定義された時点での継続（恐らくはトップレベル）に束縛する．
ccを呼び出すことでfailはトップレベルまで一気に戻ることができる．
\reffig{fig:ChoseFailInScheme}の実装は*paths*をスタックとして使っており，
失敗のときには必ず一番近いchoiceまで戻る．
この戦略は時系列バックトラックと呼ばれ，結果的に問題空間の深さ優先探索を行うことになる．
「非決定性」という言葉はしばしば深さ優先の実装の同義語かのように使われる．
非決定的アルゴリズムについてのFloydの古典的な論文では「非決定性」をこの意味で使っており，
またこれは非決定的パーザやPrologで使われているものでもある．
しかし\reffig{fig:ChoseFailInScheme}の実装は唯一可能なものという訳ではなく，
正しくすらないということに注意して欲しい．
原則的にはchooseは任意の計算可能な条件を満たすようなオブジェクトを選べるべきだ．
しかし上のchooseとfailを使ってグラフを探索するプログラムは，
グラフが閉路を含んでいると永久に終了しないかもしれない．
(define *paths* ())
(define failsym '@)
(define (choose choices)
(if (null? choices)
(fail)
(call-with-current-continuation
(lambda (cc)
(set! *paths*
(cons (lambda ()
(cc (choose (cdr choices))))
*paths*))
(car choices)))))
(define fail)
(call-with-current-continuation
(lambda (cc)
(set! fail
(lambda ()
(if (null? *paths*)
(cc failsym)
(let ((p1 (car *paths*)))
(set! *paths* (cdr *paths*))
(p1)))))))
\caption{chooseとfailのSchemeによる実装．}
\label{fig:ChoseFailInScheme}
現実的には，
非決定性とはすなわち\reffig{fig:ChoseFailInScheme}に示した深さ優先探索を行うことであり，
探索空間のループを避ける方法はプログラマに委ねられている．
しかし興味のある読者のために，この章の最終節では本物のchooseとfailの実装方法を示した．
この節ではCommon Lispにおいてchooseとfailを書く方法を示す．
前節で見たように，call/ccはSchemeで非決定性を実現するときに役立った．
継続は，計算の未来という理論的概念を具現化したものを提供する．
Common Lispでは代わりに第20章の継続渡しマクロを使う．
これらのマクロを使うとchooseは前節のScheme版に比べて少々汚くなるが，
それでも実質的には等価になる．
(defparameter *paths* nil)
(defconstant failsym '@)
(defmacro choose (&rest choices)
(if choices
`(progn
,@(mapcar #'(lambda (c)
`(push #'(lambda () ,c) *paths*))
(reverse (cdr choices)))
,(car choices))
'(fail)))
(defmacro choose-bind (var choices &body body)
`(cb #'(lambda (,var) ,@body) ,choices))
(defun cb (fn choices)
(if choices
(progn
(if (cdr choices)
(push #'(lambda () (cb fn (cdr choices)))
*paths*))
(funcall fn (car choices)))
(fail)))
(defun fail ()
(if *paths*
(funcall (pop *paths*))
failsym))
\caption{Common Lispによる非決定的オペレータ．}
\label{fig:NoneterministicOpInCL}
\reffig{fig:NoneterministicOpInCL}にはCommon Lispによるfailの実装と，
2種類のchooseの実装を示した．
Common Lispのchooseの構文はScheme版とは少々異なる．
Schemeのchooseは，値を選ぶための選択肢リストを1つ引数に取った．
Common Lisp版はprognと同じ構文になっている．
引数には任意個の式を渡し，それらから評価される式が選ばれる．
> (defun do2 (x)
(choose (+ x 2) (* x 2) (expt x 2)))
DO2
> (do2 3)
5
> (fail)
6
トップレベルでは，非決定的な探索の背後にあるバックトラッキングが明確に見えてくる．
変数*paths*はまだ辿っていない経路を保存するために使われる．
計算が複数の選択肢を持つchooseに辿り着くと，
最初の選択肢が評価され，残りは*paths*に保存される．
後にプログラムがfailに出会うと，
最後に保存された選択肢が*paths*からポップされ，再始動する．
再始動するための選択肢が残っていないときは，failは特別な値を返す．
> (fail) 9 > (fail) @
\reffig{fig:NoneterministicOpInCL}では定数failsymは失敗を表すが，
シンボル@として定義されている．
@も通常の返り値に含めたいときは代わりにgensymをfailsymにすればよい．
非決定的な選択オペレータには他にchoose-bindがあるが，こちらは構文が多少異なる．
引数にはシンボルと選択肢のリストと実行本体となるコードを取る．
choose-bindは選択肢のリストにchooseを適用し，
選ばれた値を渡されたシンボルに束縛し，その下でコードを評価する．
> (choose-bind x '(marrakesh strasbourg vegas)
(format nil "Let's go to ~A." x))
"Let's go to MARRAKESH."
> (fail)
"Let's go to STRASBOURG."
Common Lisp版の実装でオペレータchoiceを提供しているのは単に簡便のためだ．
chooseの機能は，choose-bindがあれば十分得られる．
chooseを使う次のコードは，
(choose (foo) (bar))
次のように変換すればよい．
(choose-bind x '(1 2)
(case x
(1 (foo))
(2 (bar))))
しかしこの場合は別々のオペレータがあった方が読み易くなる
\footnote{望みとあらば，このコードが外部に見せるインタフェイスはオペレータ一つだけでもよい．
(fail)は(choose)と等価だからだ．}．
Common Lisp版のオペレータchoiceは，クロージャと変数捕獲により関連する変数の束縛を保存する．
chooseとchoose-bindはマクロなので，それを包む式のレキシカル環境の中で展開される．
それらが*paths*にプッシュするものは保存される選択肢を含むクロージャで，
その中で参照されているレキシカル変数の全ての束縛を閉じ込めていることに注意．
例えば次の式では，
(let ((x 2))
(choose
(+ x 1)
(+ x 100)))
xの値は保存された選択肢が再始動するときに必要になる．
だからこそchooseは引数をλ式で包むように書かれているのだ．
上の式は次のようにマクロ展開される．
(let ((x 2))
(progn
(push #'(lambda () (+ x 100))
*paths*)
(+ x 1)))
*paths*に保管されるオブジェクトはxへのポインタを含むクロージャだ．
SchemeとCommon Lispとでオペレータchoiceの構文が違うのは，
クロージャ内の変数を保存する必要があるためだ．
chooseとfailを第20章の継続渡しマクロと共に使うと，
継続を保持する変数*cont*へのポインタも同様に保管される．
関数を=defunで定義し，=bindで呼び出し，
その中では=valuesで値を返すようにすることで，
任意のCommon Lispプログラムで非決定性が利用できるようになる．
(=defun two-numbers ()
(choose-bind n1 '(012345)
(choose-bind n2 '(0 12345)
(=values n1 n2))))
(=defun parlor-trick (sum)
(=bind (n1 n2) (two-numbers)
(if (= (+ n1 n2) sum)
`(the sum of ,n1 ,n2)
(fail))))
\caption{サブルーチン内でCommon Lisp版のchoiceを使う．}
\label{fig:CommonLispChoiceInASubroutine}
これらのマクロを使うと，サブルーチン内で非決定的な選択を行う例をうまく動作させることができる．
\reffig{fig:CommonLispChoiceInASubroutine}にはCommon Lisp版のparlor-trickを示した．
この動作はScheme版と同様だ．
> (parlor-trick 7) (THE SUM OF 2 5)
これが動作するのは，
(=values n1 n2)
という式がchoose-bindsの中で次のようにマクロ展開されるからだ．
(funcall *cont* n1 n2)
choose-bindはそれぞれ順に，
本体内で参照されている全ての変数（*cont*など）へのポインタを保持しているクロージャへと
マクロ展開される．
choose，choose-bindとfailの使い方に関する制限は
\reffig{fig:RestrictionsContPassMacros}で示した継続渡しマクロを使うコードの制限と同じだ．
choiceを使うときは，それが最後に評価されなければならない．
よってCommon Lisp版のchoiceを連続して使いたいときは入れ子にしなければならない．
> (choose-bind first-name '(henry william)
(choose-bind last-name '(james higgins)
(=values (list first-name last-name))))
(HENRY JAMES)
> (fail)
(HENRY HIGGINS)
> (fail)
(WILLIAM JAMES)
これは今までと同様に深さ優先探索になる．
第20章で定義したオペレータには最後に評価されなければならないという際だった制限があった．
この制限は新たなマクロの層では別の形として現れる．
=valuesはchooseの中で使わなければならず，その逆はできない．
すなわち次のコードは動作するが，
(choose (=values 1) (=values 2))
次のコードは動作しない．
(=values (choose 1 2)) ; 誤り
（後者では=valuesの展開形内に出てくる*cont*を
chooseの展開形が捕捉できない．）
> (=defun descent (n1 n2)
(cond ((eq n1 n2) (=values (list n2)))
((kids n1) (choose-bind n (kids n1)
(=bind (p) (descent n n2)
(=values (cons n1 p)))))
(t (fail))))
DESCENT
> (defun kids (n)
(case n
(a '(b c))
(b '(d e))
(c '(d f))
(f '(g))))
KIDS
> (descent 'a 'g)
(ACFG)
> (fail)
@
> (descent 'a 'd)
(ABD)
> (fail)
(ACD)
> (fail)
@
> (descent 'a 'h)
@
\caption{Common Lispにおける非決定的探索．}
\label{fig:NondetSearchInCL}
ここと\reffig{fig:RestrictionsContPassMacros}で示された制限に従う限り，
Common Lispでも非決定的選択がSchemeと同様に機能する．
\reffig{fig:NondetSearchInCL}には
\reffig{fig:NoneterministicTreeSearch}で示した非決定的なツリーの探索プログラムのCommon Lisp版を示した．
Common Lisp版descentは，少々長くて読み辛いが，直訳で書ける．
こうしてバックトラックを陽に使わなくとも非決定的探索が可能なCommon Lispユーティリティが手に入った． それらを書く手間をかけた後は， それら無しでは長くごちゃごちゃとなりそうなプログラムをわずかな行数で書くことで利点を享受できる． ここで提示したユーティリティの上にさらにマクロの層を重ねることで， ATNコンパイラを1ページ分のコード（第23章）で， Prologのプロトタイプを2ページ分のコード（第24章）で実現できる．
chooseを使うCommon Lispプログラムは
末尾呼び出しの最適化を行ってコンパイルしなければならない
---速くするためだけでなく，スタック空間を使い果たすのを避けるためだ．
継続を呼び出すことで値を「返す」プログラムからは，実際には最後に失敗するまで決して制御が戻らない．
末尾呼び出しを最適化しないと，スタックはひたすら伸び続けてしまう．
この節では非決定的選択を行うSchemeプログラムでカットを使う方法を示す． カットという言葉はPrologから来ているが，その概念そのものは一般の非決定性で通用する． 非決定的選択を行うどのようなプログラムでもカットは使えるとうれしい．
カットはPrologとは独立して考えると分かり易い． 現実的な例を考えてみる． Chocoblobキャンディーの製造元が販促活動を始めるとしよう． キャンディーのうち何箱かには当たりの印のメダルが入っている． 公平にするため，同じ街に2つ以上の当たり箱が送られないようにする．
販促活動の開始後，当たりの印のメダルが小さいので子供が飲み込む恐れがあることが分かった． 法的な観点に駆り立てられ，Chocoblob社の法務部は全ての当たり箱を必死に探すことになった． Chocoblobキャンディーを扱う店は街ごとにいくつもあり， キャンディーの箱は店ごとにいくつもある． しかし検査のためには全部の箱を開ける必要はない． ある街で当たり箱を1つ見つければ，その街では他の箱を開ける必要は一切ない． ある街にある当たり箱は高々1つだからだ． そしてこれを実現するのがカットなのだ．
カットとは何かというと，検索ツリーの一部分だ． キャンディー会社の例では検索ツリーは物理的に存在した． ルート・ノードは会社の統括オフィスだ． ルート・ノードの子ノードは当たり箱の送られた街で，それらの子ノードはそれぞれの街の店， そしてそれらの子ノードは店の中のキャンディーの箱を表す． このツリーに対し検索を行う法務部が当たり箱の一つを見つけたときは， 現在いる街から伸びる全ての未探索の枝を枝刈りできる．
実際はカットには2つの動作が絡む． カットを行うのは検索ツリーのある部分が不要と分かったときだが， 最初にツリーのカットできる部分にマークを付けなければならない． キャンディー会社の例では，ツリーへのマークは街を訪れるときにすればよいとすぐに分かる． Prologのカットが何を行うのかを抽象的に説明するのは難しい． マークが暗黙のうちに行われるからだ． マークを陽につけるオペレータがある方がカットの動作は理解し易い．
(define (find-boxes)
(set! *paths* ())
(let ((city (choose '(la ny bos))))
(newline)
(let* ((store (choose '(1 2)))
(box (choose '(1 2))))
(let ((triple (list city store box)))
(display triple)
(if (coin? triple)
(display 'c))
(fail)))))
(define (coin? x)
(member x '((la 1 2) (ny 1 1) (bos 2 2))))
\caption{当たりキャンディー検索の網羅的な例．}
\label{fig:ExhaustiveChocoblobSearch}
\reffig{fig:ExhaustiveChocoblobSearch}には
キャンディー会社の例のツリーの小さいものに対し非決定的に検索を行うプログラムを示した．
箱を開けてみるたびにプログラムは(街 店 箱)のリストを表示する．
箱にメダルが入っていたらその後にcが表示される．
> (find-boxes) (LA 1 1) (LA 1 2) C (LA 2 1) (LA 2 2) (NY 1 1) C (NY 1 2) (NY 2 1) (NY 2 2) (BOS 1 1) (BOS 1 2) (BOS 2 1) (BOS 2 2) C @
上でキャンディー会社の発見した効率の良い検索方法を実装するには，
2つの新しいオペレータが必要になる．
markとcutだ．
\reffig{fig:MarkingAndPruningSearchTrees}にはそれらの実装例を示した．
非決定性そのものは個々の実装とは独立して考えられるが，
検索ツリーの枝刈りは最適化手法であり，chooseの実装法に強く依存する．
\reffig{fig:MarkingAndPruningSearchTrees}に示したmarkとcutは
深さ優先の実装によるchooseに適している．
(define (mark) (set! *paths* (cons fail *paths*)))
(define (cut)
(cond ((null? *paths*))
((equal? (car *paths*) fail)
(set! *paths* (cdr *paths*)))
(else
(set! *paths* (cdr *paths*))
(cut))))
\caption{検索ツリーのマークと枝刈り．}
\label{fig:MarkingAndPruningSearchTrees}
markの基本的な仕組みは，マークを未探索の分岐点のリスト*paths*に保存することだ．
cutを呼ぶと一番近いマークへの全ての経路を*paths*からポップする．
さてマークには何を使おう？
例えばシンボルmを使う方法もあるが，
そうするとfailはmに出会ったときに無視するよう書き直さなければならない．
うまいことに，関数もデータオブジェクトだから，
failがそのまま使えるマークが少なくとも一つある．
それは関数failそのものだ．
するとfailがマークとして現れたとき，単に自分自身を呼び出すことになる．
(define (find-boxes)
(set! *paths* ())
(let ((city (choose '(la ny bos))))
(mark) ; 変更
(newline)
(let* ((store (choose '(1 2)))
(box (choose '(1 2))))
(let ((triple (list city store box)))
(display triple)
(if (coin? triple)
(begin (cut) (display 'c))) ; 変更
(fail)))))
\caption{当たりキャンディー検索の枝刈りを用いた例．}
\label{fig:PrunedChocoblobSearch}
\reffig{fig:PrunedChocoblobSearch}にはそれらのオペレータを使って
キャンディー会社の例の検索ツリーで枝刈りをする方法を示した．
（変更のあった行はセミコロンで示した．）
新たな街を訪れるごとにmarkを呼ぶ．
その時点では*paths*には「残りの街で検索を行う」という一つの継続が含まれる．
当たり箱を見つけたときにはcutを呼ぶ．
すると*paths*は最後にmarkを呼んだ時点の値に戻る．
cutの効果は次にfailを呼ぶときまでは明らかにならない．
しかしそのときになると，当たり発見の表示の後，
次に呼び出されたfailは，途中に尽くされていない選択肢があっても，
処理を一番根元のchooseまで戻す．
要するに，当たり箱を見つけたら即座に次の街の検索に移ることになる．
> (find-boxes) (LA 1 1) (LA 1 2) C (NY 1 1) C (BOS 1 1) (BOS 1 2) (BOS 2 1) (BOS 2 2) C @
こうすると12個も箱を開けなくとも，7個で済む．
(define (path node1 node2)
(bf-path node2 (list (list node1))))
(define (bf-path dest queue)
(if (null? queue)
'@
(let* ((path (car queue))
(node (car path)))
(if (eq? node dest)
(cdr (reverse path))
(bf-path dest
(append (cdr queue)
(map (lambda (n)
(cons n path))
(neighbors node))))))))
\caption{決定的な検索．}
\label{fig:DeterministicSearch}
グラフに対する決定的な検索プログラムは，
ループに捕まるのを避けるための手立てを陽に講じなければならない．
\reffig{fig:DirectedGraphWithLoop}にはループのある有向グラフを示した．
ノードaからノードeまでの経路を探すプログラムには
a, b, cから成るループに捕まる危険がある．
決定的な手法では，乱数や広さ優先探索を使うか，ループを陽に検出しない限り，
検索はいつまでも終了しないかもしれない．
\reffig{fig:DeterministicSearch}に示したpathの実装は
広さ優先探索によってループを避けている．
(define (path node1 node2)
(cond ((null? (neighbors node1)) (fail))
((memq node2 (neighbors node1)) (list node2))
(else (let ((n (true-choose (neighbors node1))))
(cons n (path n node2))))))
\caption{非決定的な検索．}
\label{fig:NondeterministicSearch}
原則としては，
非決定性を使うとループに対する考慮すら省くことができるはずだ．
第22--3節で与えた，深さ優先のchooseとfailの実装はループに捕まる危険性を孕んでいるが，
几帳面にやれば，
非決定的なchooseが計算可能な仕様を満たす任意のオブジェクトを選べるようにできる．
この例も例外ではない．
chooseを適切に書いておけば，
\reffig{fig:NondeterministicSearch}に示したようにpathを短く簡潔に書ける．
(define *paths* ())
(define failsym '@)
(define (true-choose choices)
(call-with-current-continuation
(lambda (cc)
(set! *paths* (append *paths*
(map (lambda (choice)
(lambda () (cc choice)))
choices)))
(fail))))
(define fail)
(call-with-current-continuation
(lambda (cc)
(set! fail
(lambda ()
(if (null? *paths*)
(cc failsym)
(let ((p1 (car *paths*)))
(set! *paths* (cdr *paths*))
(p1)))))))
（SchemeのmapはCommon Lispのmapcarと同じ．）
choose．}
\label{fig:CorrectChooseInScheme}
この節ではループに対しても安全なchooseとfailの実装方法を示す．
\reffig{fig:CorrectChooseInScheme}には真の非決定的なchooseとfailのScheme版を示した．
ここで実装したchooseとfailを使うプログラムは，
等価な非決定的アルゴリズムが解を見つけられるときにはいつでも解を見つけ，
ハード的な能力のみに制限される．
\reffig{fig:CorrectChooseInScheme}に示した真のchooseの実装は
保存された経路のリストをキューとして扱うことで機能する．
真のchooseを使うプログラムは状態空間を広さ優先で探索する．
プログラムが分岐点に到達したとき，
それぞれの選択肢を選ぶ継続が保存された経路のリストの末尾に付加される．
その後failが呼ばれるが，ここは変わっていない．
この実装のchooseを使うと，
\reffig{fig:NondeterministicSearch}の実装のpathは
\reffig{fig:DirectedGraphWithLoop}に示したグラフのaからeへの経路
（実は最短経路）を発見できる．
記述の完全性のためにこの節ではchooseとfailの本当に正しい実装を示したが，
元の実装でも大抵は十分だ．
プログラミング言語の抽象化技法の価値は，
その実装が形式的に正しくないからといって減りはしない．
プログラミング言語によっては，
利用できる最大の整数が$32767$なのに，全ての整数が利用できるかのようにコードを書くことがある．
幻想にどこまで従えるかを知っている限りほとんど危険はない
---少なくとも，実現できる抽象化と秤にかけてよい程度には少ない．
次の2つの章で示すプログラムが簡潔なのは，多くは非決定的なchooseとfailを使ったことに依る．