SICP 読み (227) 4.3.3 amb 評価器の実装
手動トレイスしてみる。まずは (list (amb 1 2 3)) で。この式は application 認定とゆー事で以下の手続きで評価される。
(define (analyze-application exp) (let ((fproc (analyze (operator exp))) (aprocs (map analyze (operands exp)))) (lambda (env succeed fail) (fproc env (lambda (proc fail2) (get-args aprocs env (lambda (args fail3) (execute-application proc args succeed fail3)) fail2)) fail))))
list が analyze されて fproc には
(lambda (env succeed fail) (succeed (lookup-variable-value 'list env) fail))
な手続きがセットされる。aprocs の方が面倒だな。てか先に (amb 1 2 3) から確認入れた方が良さげ。こっちからヤッてみよう。
amb なソレは以下で評価
(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))))
cprocs は
((lambda (env succeed fail) (succeed 1 fail)) (lambda (env succeed fail) (succeed 2 fail)) (lambda (env succeed fail) (succeed 3 fail)))
なリストとして (amb 1 2 3) が戻す手続きは
(lambda (env succeed fail) (define (try-next choices) (if (null? choices) (fail) ((car choices) env succeed (lambda () (try-next (cdr choices)))))) (try-next '((lambda (env succeed fail) (succeed 1 fail)) (lambda (env succeed fail) (succeed 2 fail)) (lambda (env succeed fail) (succeed 3 fail)))))
になりますな。違う。(analyze (amb 1 2 3)) が戻す手続きだ。