analyze-ambについて
p258 analyze-amb の動作を確認しよう。
(begin (amb1 1 2)
3
(amb2))
という例を考える。
(1) 継続処理列の確認
begin の処理する継続処理の列は
amb1 → 3 → amb2
である。合成λパックは
(amb1 → (3 → amb2))
となる。しかし我々の望む継続処理は
(amb1返値1 → (3 → amb2返値null)) ⇒ (amb1返値2 → (3 → amb2返値null)) ⇒ (amb1返値null) ⇒ f0 ① ② ③ ④ ⑤ ⑥
である。青い矢印 ⇒ のところで、継続処理が begin の用意したものを越えて進んでいる。
先に答えを言ってしまえば、赤い矢印は成功継続処理で、青い矢印は失敗継続処理である。amb が begin の用意した成功継続の枠を破って、失敗継続を呼び出している。
図から、
amb は自分のリストが null のときは失敗継続処理を継続させる。 null 以外のときは成功継続処理を継続させる。
ということが分かる。
(2) 継続処理の出処の確認
また図より、継続処理列中の各 amb が受け取る継続処理がどんなものか想像してみよう。
①amb1の受け取る成功継続は (3 → amb2)、失敗継続は (デフォルトのf0) ②amb2の受け取る成功継続は (デフォルトのs0)、失敗継続は (amb1'(2) → 3 → amb2) ③amb1の受け取る成功継続は (3 → amb2)、失敗継続は (デフォルトのf0) ④amb2の受け取る成功継続は (デフォルトのs0)、失敗継続は (amb1'()) ⑤amb1の受け取る成功継続は (デフォルトのs0)、失敗継続は (デフォルトのf0)
という感じかと思われる。
各継続の出処を考えよう。①③の成功継続は begin が用意したものだ。また、デフォルトs0、f0 はbeginの引数である。
出処不明なのは、②④の失敗継続である。これは一体だれが作ったのか？
先に答えを言ってしまうと、②amb2の失敗継続は①amb1が作る。④amb2の失敗継続は③amb1が作る。
作り方は、「①のリストのcdr + ①の成功継続」、「③のリストのcdr + ③の成功継続」という感じで作る。この作業は p258 analyze-ambのtry-nextの中で行っている。
try-next はこのように失敗継続の作成のほか、成功継続の本体としての役目、 さらにまた失敗継続の中の再帰関数としての役目もある。
ambは一種のループだから、ループを実現するための再帰が存在する筈である。それがこのtry-nextの再帰である。
(3) 継続処理の伝搬方法
(i)失敗継続の伝搬方法
そして、①amb1で作られた失敗継続は、λパック、若しくは成功継続の引数として、3 そして ②amb2 へと伝えられていく。(失敗継続のたらいまわし)。
失敗継続の中身は、再帰 try-next であるが、これは伝搬中は発動しない。たらいまわし先(amb2のリストがnullの場合)で発動する。大回りな再帰処理とも見れる。
(ii)成功継続の伝搬方法
③の成功継続はbeginの作ったものだが、beginが直接渡す相手は①である。③にまで伝搬するのにはトリックがある。
①amb1 は begin から貰った成功継続を、自分が作る失敗継続の中に埋め込むのである。(p258 analyze-ambのtry-nexの中にsucceedが埋め込まれている。そしてtry-next自身が失敗継続として使われている。)。この失敗継続は、たらいまわしによって③に伝搬される。このとき埋め込まれた成功継続も一緒に伝搬する。
実行を追いかけると以上の動作をしていることが確認できる筈である。
しかし今回は f を無視できないので、若干ややこしさが倍増している。env は無視している。
(λbegin s0 f0)
↓
((λ(s f) ← begin の作る合成関数
(λamb1 ← amb1 と (3 → amb2) の合成
(λ(v f1) ← λamb1の成功継続
(λ3λamb2 s f1)) ← (3 → amb2)の合成部分
f))
s0 f0)
↓
(λamb1
(λ(v f1)
(λ3λamb2 s0 f1))
f0)
↓
((λ(s f) ← p.258 analyze-amb でλamb1を展開
(define (try-next choices) ← try-next の定義
(if (null? choices) ← ambのリストによって失敗継続と、成功継続を振り分ける
(f) ← ambのリストがnullのときは失敗継続を継続させる(=呼び出す)
((car chices) ← ambのリストがnull以外のときは成功継続を継続させる(=呼び出す)
s ← ここで引数の成功継続s(中身は(3→amb2))を try-next に埋め込んでいる
(λ() (try-next (cdr choices))))))
(try-next '(λ1 λ2))) ← λamb1の展開はここまで。'(λ1 λ2)はamb1のリスト'(1 2)のλパック化リスト
(λ(v0 f1) ← λamb1に渡す成功継続
(λ3λamb2 s0 f1)) ← 成功継続の中身は(3 → amb2)合成関数である。
f0) ← λamb1に渡す失敗継続
↓
(define (try-next choices) ← amb1の最初の実行時のtry-next定義
(if (null? choices)
(f0) ← (f0もtry-nextに埋め込まれています。⑥で使います)
((car chices)
(λ(v0 f1)
(λ3λamb2 s0 f1)) ← try-nextに(3→amb2)が埋め込まれました
(λ() (try-next (cdr choices)))))) ← 失敗継続で、try-nextを再帰する。
(try-next '(λ1 λ2)) ← try-next実行
↓
(if (null? '(λ1 λ2)) ← ambのリストが
(f0) ← null なら失敗継続 f0 を継続させる
(λ1 ← null 以外なら成功継続(1→(3→amb2))を継続させる
(λ(v0 f1)
(λ3λamb2 s0 f1))
(λ() (try-next '(λ2))))) ← λ1の失敗継続にλamb1の作ったtry-nextがたらいまわしされています。
↓
(λ1 ← λ1 はλamb1のリスト'(1 2)の最初の式1のλパックである
(λ(v0 f1)
(λ3λamb2 s0 f1))
(λ() (try-next '(λ2))))
↓
((λ(s f) (s 1 f)) ← λ1
(λ(v0 f1) ← 成功継続
(λ3λamb2 s0 f1)) ← (3→amb2)合成関数
(λ() (try-next '(λ2)))) ← 失敗継続。λamb1の作ったものがたらいまわしされています。再帰された try-next はたらいまわし先で発動します。
↓
((λ(v0 f1) ← 成功継続実行
(λ3λamb2 s0 f1))
1 ← amb1 の返値1実行。(引数は先に評価される)
(λ() (try-next '(λ2)))) ← 成功継続にλamb1の作った失敗継続がたらいまわしされています
↓
(λ3λamb2 s0 (λ() (try-next '(λ2))))) ← (3→amb2)にλamb1の作った失敗継続がたらいまわしされています
以上で、 ① → ② の部分をみた。
一番最後の行で、合成関数 (3 → amb2) に amb1 で作った失敗継続 (λ(try-next '(λ2)))がたらいまわしされているのが確認できる。
また少し上に遡るが、この失敗継続の中の try-next には、(3 → amb2)合成関数が埋め込まれているのが確認できる。
さらに実行を進めると、② → ③ の部分を確認できる筈だが、、、疲れたので省略
(s0について。s0 は begin の全体の成功継続である。s0 もちゃんと try-nextに埋め込まれているが、上の例だと amb2 が常にnil なので s0 に継続が移動することはない。amb2 が nil 以外を返す例なら s0 に進む。この場合 amb1 をループさせるのは p.259 driver-loop の役目となる。)