amb と require の動作の確認
amb1 ... amb2 ... require ...
- require が失敗すると、require の前に実行された amb2 に処理が戻る
- amb2 はバックトラックして、その位置からプログラムが再実行する
- amb2 のリストが終了してて バックトラックできない場合、その前のamb1 に戻る(バックアップ)
- amb1 もバックトラックしてその位置からプログラムが再実行する
- amb1 のリストが終了していてバックトラックできない場合、前の amb に戻りたいが、ないので先頭まで戻って終了する。
- require が成功した場合は、そのまま下の式を実行してプログラムの最後まで行って終了する。
- プログラムの最後まで行って終了した場合、評価器の駆動ループが (require false) を発行して処理を前の amb に戻す。
図にするとこんな感じ
なお、require 失敗時の戻り先の amb をどれにするかは、関数の親子関係には全く関係がない。また、実行フレームの親子関係にも全く関係ない。関係あるのは、実行の順番だけである。require より以前に実行された amb に戻ることになっている。例えば
(define (f)
...
(amb 1 2 3)
...)
(define (g) (require false))
(begin ...
f
...
g)
を実行した場合、g の中の require の失敗時の戻り先は、f の中の amb である。なぜなら、f の中の amb は、require より以前に実行されているからである。
まとめると、基本的な動作は、(amb ...) を実行して、リストが終わっていた場合、その前に実行した amb に戻る(バックアップ)ということである。
require の失敗というのは、(amb) を実行することである。これはambのバックアップ動作を利用して前の amb に戻っているのである。
逆に言えば、無条件に以前の amb に戻りたいときは、(require false) とか (amb) を実行すればよいということである。
Ex. 4.35
p.246 の an-element-of 、an-integer-starting-from と同じようにつくる
(define (an-integer-between s e) (require (<= s e)) (amb s (an-integer-between (+ s 1) e)))
Ex. 4.36
i, j, k が無限ストリームになった場合の探索の様子を見てみる
こんな感じで、探索が k の無限ストリームにつかまって返ってこなくなる。
探索ツリーの途中や末端が無限ストリームになると、探索が返ってこなくなる。なので、 修正方法は、最初のストリームだけ無限にして、途中や末端のストリームは有限にすることである。
(define (a-pythagorean-triple-between low high)
(let ((k (an-integer-starting-from low)))
(let ((i (an-integer-between low k)))
(let ((j (an-integer-between i k)))
(require (= (+ (* i i) (* j j)) (* k k)))
(list i j k)))))
i, j は三角形の短辺、k は三角形の長辺を指している。短辺は長辺より長くなることはないので。
Ex. 4.37
2重の amb に対して、2重の require がある場合。
amb1 amb2 require1 require2
こんな感じ。この場合、この本の評価器の行う探索は、
- require1 によるツリーの枝刈りは行わない。ツリーは全て探索される。
- require1、require2 が2つあるからといって、探索を2回行うことはない。探索は1回だけである。
である。まとめると、評価器は amb1、amb2 の作るツリーの全体を1度だけ探索する。ということである。
枝刈りをしないので、効率の良い悪いは、単純にツリーの大小で比べられる。
で、low=1, high=5 のとき、Benさんのプログラムの探索ツリーは、こんな感じになる。
調査の必要な枝は 15本。一方、前問(Ex. 4.35)は amb が3重になっており、探索ツリーはこんな感じになる。
調査の必要な枝は 35本である。Benさんのほうが効率が良い。