われわれは4.1.7節の解析評価器を修正し, 非決定性Schemeのamb評価器を構成しよう.55 その式の評価は, 解析評価器のように式の解析で作った 実行手続きを呼び出すことで実現する. 通常のSchemeの解釈と非決定性Schemeの解釈の相違は, すべて実行手続きにある.
値を受け取り, 計算を続行するのが成功継続の仕事である. 値とともに, 成功継続は失敗継続も受けとる. それは後に, その値が袋小路に導いた時, 呼び出される.
非決定性プロセスの別の道を試みるのが失敗継続の仕事である. 非決定性言語の本質は, 式は分岐の選択を表現出来るという事実にある. そういう式の評価は, その選択が受け入れ可能な結果に至るかどうかが前もって分らなくても, 示された分岐選択の一つへ進まなければならない. これに対処すべく, 評価器は分岐の一つを取り上げ, その値を成功継続へ渡す. この値とともに, 評価器は後に別の分岐を選ぶ時に呼び出される失敗継続を構成し, 渡す.
評価の最中に, (例えばrequireの呼出しは結果として常に失敗する式(amb)の実行になる---4.3.1節参照)利用者のプログラムが積極的に現在の試行を拒絶した時, 失敗が惹き起される(つまり, 失敗継続が呼び出される). その時点で手元にある失敗継続は, 直前の選択点に別の分岐を選択させる. この選択点に, 考慮すべき分岐が残っていなければ, その前の選択点での失敗が惹き起され, これを繰り返す. 失敗継続はまた駆動ループから, try-again要求への応答として, 式の別の値を見出すべく呼び出される.
加えて(変数への代入のような)副作用の演算が選択の結果のプロセスの枝で起きると, プロセスが袋小路に出会った時, 新しい選択をする前に, この副作用をやり戻す必要があるかも知れない. これは副作用に, 副作用をやり戻し, 失敗を伝搬する失敗継続を作らせることで実現出来る.
要約すると失敗継続が構成されるのは次による.
• amb式---amb式の作った現在の選択が袋小路に至った時, 別の選択をする機構を用意するため;
• トップレベルの駆動ループ---選択を使い切った時, 失敗を報告する機構を用意するため;
• 代入---失敗を横取りし, バックトラック中に代入を元へ戻すため.
失敗は袋小路に出会った時だけ起動される. これが起きるのは次の場合である.
• 利用者プログラムが(amb)を実行した時;
• 利用者が駆動ループでtry-againを入力した時.
失敗継続は, 失敗の処理中にも呼び出される.
• 代入が作り出した失敗継続が, 副作用のやり戻しを完了した時,
この代入に至った選択点まで, または駆動ループまで失敗を伝搬し戻すため, それが横取りした失敗継続を呼び出す.
• あるambの失敗継続が, 選択を使い切った時, 直前の選択点か駆動ループまで失敗を伝搬し戻すため, このambに元々与えられた失敗継続を呼び出す.
(define (amb? exp) (tagged-list? exp 'amb)) (define (amb-choices exp) (cdr exp))またanalyzeの振分け部に, この特殊形式を認識し, 適切な実行手続きを生成する節を追加しなければならない:
((amb? exp) (analyze-amb exp))
トップレベルの手続きambeval(4.1.7節にあったevalの版と同様) は, 与えられた式を解析し, 結果の実行手続きを与えられた環境と二つの与えられた継続とに作用させる:
(define (ambeval exp env succeed fail) ((analyze exp) env succeed fail))
成功継続は二引数: まさに得られた値と, この値がその後の失敗に導く時に使うべき, もう一つの失敗継続をとる手続きである. 失敗継続は引数なしの手続きである. そこで 実行手続きの一般形は
(lambda (env succeed fail) ;; succeed は (lambda (value fail) ...) ;; fail は (lambda () ...) ...)である.
例えば
(ambeval ⟨exp⟩
the-global-environment
(lambda (value fail) value)
(lambda () 'failed))
の実行は, 与えられた式⟨exp⟩を評価しようとし, (評価が成功すれば)式の値か,
(評価が失敗すれば)記号failedかのいずれかを返す. 次に示す駆動ループでambevalを呼び出すと, ループを継続し, try-againの要求に応じる, 遥かに複雑な継続手続きを使う.
amb評価器の複雑さの殆んどは実行手続きが互いに呼び出す時の, 継続を引き渡す機構に由来する. 次のプログラムに従って, 実行手続きのそれぞれを, 4.1.7節の通常の評価器の対応する手続きと比べるべきである.
(define (analyze-self-evaluating exp)
(lambda (env succeed fail)
(succeed exp fail)))
(define (analyze-quoted exp)
(let ((qval (text-of-quotation exp)))
(lambda (env succeed fail)
(succeed qval fail))))
(define (analyze-variable exp)
(lambda (env succeed fail)
(succeed (lookup-variable-value exp env)
fail)))
(define (analyze-lambda exp)
(let ((vars (lambda-parameters exp))
(bproc (analyze-sequence (lambda-body exp))))
(lambda (env succeed fail)
(succeed (make-procedure vars bproc env)
fail))))
変数の探索は常に「成功する」ことに注意しよう. lookup-variable-valueが変数を見出すことが出来なければ, いつものようにエラーとする. そういう「失敗」は, プログラムの虫---未束縛の変数の参照---であって, これはわれわれは現在試みているものの代りに, 他の非決定性選択を試みるべきであるという表示ではない.
(define (analyze-if exp)
(let ((pproc (analyze (if-predicate exp)))
(cproc (analyze (if-consequent exp)))
(aproc (analyze (if-alternative exp))))
(lambda (env succeed fail)
(pproc env
;; pred-valueを得るための
;; 述語の評価の成功継続
(lambda (pred-value fail2)
(if (true? pred-value)
(cproc env succeed fail2)
(aproc env succeed fail2)))
;; 述語の評価の失敗継続
fail))))
並びも下請け手続きsequentiallyの継続渡しに必要な計略を除き, 以前の評価器におけるのと同様に扱う. つまりaに続きbを逐次的に実行するには, bを呼び出す成功手続きをもってaを呼び出す.
(define (analyze-sequence exps)
(define (sequentially a b)
(lambda (env succeed fail)
(a env
;; aを呼び出す時の成功継続
(lambda (a-value fail2)
(b env succeed fail2))
;; aを呼び出す時の失敗継続
fail)))
(define (loop first-proc rest-procs)
(if (null? rest-procs)
first-proc
(loop (sequentially first-proc (car rest-procs))
(cdr rest-procs))))
(let ((procs (map analyze exps)))
(if (null? procs)
(error "Empty sequence -- ANALYZE"))
(loop (car procs) (cdr procs))))
(define (analyze-definition exp)
(let ((var (definition-variable exp))
(vproc (analyze (definition-value exp))))
(lambda (env succeed fail)
(vproc env
(lambda (val fail2)
(define-variable! var val env)
(succeed 'ok fail2))
fail))))
代入は更に面白い. これは継続をたらい回しにするのでなく, 実際に使う初めての場所である. 代入の実行手続きは, 定義のそれのように始る: 変数に代入すべき新しい値を得ようと試みる. このvprocの評価が失敗すれば, 代入は失敗する.
しかしvprocが成功し, 代入の実行に取り掛るなら, 計算のこの道が後に失敗し, 代入のバックトラックが必要になる可能性を考えなければならない. そこで, バックトラック処理の一部として, 代入のやり戻しの準備をする.57
このことは(次に注釈*1*で示すように)変数に新しい値を代入し, 代入から進行するする前に昔の値を保存する成功継続をvprocに与えることで実現する. 代入の値とともに渡される(次に注釈*2*で示す)失敗継続は, 失敗を継続する前に, 変数を昔の値に戻す. つまり成功する代入は, 後の失敗を横取りする失敗継続を準備する; 失敗が何を呼び出しても, fail2はその代りにこの手続きを呼び出し, 実際にfail2を呼び出す前に, 代入を戻す.
(define (analyze-assignment exp)
(let ((var (assignment-variable exp))
(vproc (analyze (assignment-value exp))))
(lambda (env succeed fail)
(vproc env
(lambda (val fail2) ; *1*
(let ((old-value
(lookup-variable-value var env)))
(set-variable-value! var val env)
(succeed 'ok
(lambda () ; *2*
(set-variable-value! var
old-value
env)
(fail2)))))
fail))))
(define (analyze-application exp)
(let ((pproc (analyze (operator exp)))
(aprocs (map analyze (operands exp))))
(lambda (env succeed fail)
(pproc env
(lambda (proc fail2)
(get-args aprocs
env
(lambda (args fail3)
(execute-application
proc args succeed fail3))
fail2))
fail))))
get-argsでは, aproc実行手続きのリストのcdrダウンと, 結果のargsのリストのconsアップが, リスト中の各aproc を再帰的にget-argsを呼び出す成功継続を引数として呼び出すことで実現していることに注意しよう. get-argsの再帰的呼出しのそれぞれは, その値が新しく得られた引数のすでに蓄積された引数リストへのconsである成功手続きを持っている.
(define (get-args aprocs env succeed fail)
(if (null? aprocs)
(succeed '() fail)
((car aprocs) env
;; このaprocの成功継続
(lambda (arg fail2)
(get-args (cdr aprocs)
env
;; get-argsの再帰呼出しの
;; 成功継続
(lambda (args fail3)
(succeed (cons arg args)
fail3))
fail2))
fail)))
execute-applicationで実行される実際の手続き作用は, 継続を管理する必要がある他は, 通常の評価器と同様に実現される.
(define (execute-application proc args succeed fail)
(cond ((primitive-procedure? proc)
(succeed (apply-primitive-procedure proc args)
fail))
((compound-procedure? proc)
((procedure-body proc)
(extend-environment (procedure-parameters proc)
args
(procedure-environment proc))
succeed
fail))
(else
(error
"Unknown procedure type -- EXECUTE-APPLICATION"
proc))))
(define (analyze-amb exp)
(let ((cprocs (map analyze (amb-choices exp))))
(lambda (env succeed fail)
(define (try-next choices)
(if (null? choices)
(fail)
((car choices) env
succeed
(lambda ()
(try-next (cdr choices))))))
(try-next cprocs))))
このambevalの呼出しに対する失敗継続は, 利用者にこれ以上の値はないことを知らせ, 駆動ループを再起動する.
ambevalの呼出しに対する成功継続は, 遥かに分りにくい. 得られた値を印字し, 次の分岐next-alternativeが試みられるよう, try-again手続きをもって内部ループinternal-loopを呼び出す. next-alternative手続きは成功継続へ渡された第二引数である. 通常は, この第二引数は, 現在の評価の枝が後に失敗した時に使う, 失敗継続と考える. しかし今の場合, 成功の評価は完了し, 次の成功評価を求めるためには「失敗」の分岐を起動することになる.
(define input-prompt ";;; Amb-Eval input:")
(define output-prompt ";;; Amb-Eval value:")
(define (driver-loop)
(define (internal-loop try-again)
(prompt-for-input input-prompt)
(let ((input (read)))
(if (eq? input 'try-again)
(try-again)
(begin
(newline)
(display ";;; Starting a new problem ")
(ambeval input
the-global-environment
;; ambeval 成功
(lambda (val next-alternative)
(announce-output output-prompt)
(user-print val)
(internal-loop next-alternative))
;; ambeval 失敗
(lambda ()
(announce-output
";;; There are no more values of")
(user-print input)
(driver-loop)))))))
(internal-loop
(lambda ()
(newline)
(display ";;; There is no current problem")
(driver-loop))))
internal-loopの最初の呼出しには, 現在の問題はないと文句をいって駆動ループを再起動するtry-again手続きを使う. これは進行中の評価がない時に, 利用者がtry-againを入力すると起きる振舞いである.
(define count 0)
(let ((x (an-element-of '(a b c)))
(y (an-element-of '(a b c))))
(permanent-set! count (+ count 1))
(require (not (eq? x y)))
(list x y count))
;;; Starting a new problem
;;; Amb-Eval value:
(a b 2)
;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
(a c 3)
ここでpermanent-set!の代りにset!を使ったら, どのような値が出力されるだろうか.
;;; Amb-Eval input:
(if-fail (let ((x (an-element-of '(1 3 5))))
(require (even? x))
x)
'all-odd)
;;; Starting a new problem
;;; Amb-Eval value:
all-odd
;;; Amb-Eval input:
(if-fail (let ((x (an-element-of '(1 3 5 8))))
(require (even? x))
x)
'all-odd)
;;; Starting a new problem
;;; Amb-Eval value:
8
(let ((pairs '()))
(if-fail (let ((p (prime-sum-pair '(1 3 5 8) '(20 35 110))))
(permanent-set! pairs (cons p pairs))
(amb))
pairs))
の評価の結果はどのようであろうか.
(define (require? exp) (tagged-list? exp 'require)) (define (require-predicate exp) (cadr exp))とanalyzeの振分けの新しい節
((require? exp) (analyze-require exp))とrequire式を扱う手続きanalyze-requireが必要である. analyze-requireの次の定義を完成せよ.
(define (analyze-require exp)
(let ((pproc (analyze (require-predicate exp))))
(lambda (env succeed fail)
(pproc env
(lambda (pred-value fail2)
(if ⟨??⟩
⟨??⟩
(succeed 'ok fail2)))
fail))))
55
4.2節の遅延評価器の実装には4.1.1節の通常の超循環評価器の修正を選んだ. それに対しamb評価器の基本を4.1.7節の解析評価器に置く. それはその評価器の実行手続きがバックトラック実装に便利な枠組を提供しているからである.
56
評価器では, 非決定性プログラムで使ったlet(問題4.22参照)が使えることを仮定する.
57
定義の方は,
内部定義は掃き出されると仮定するので, やり戻す心配はない(4.1.6節).