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)) が戻す手続きだ。