SICP4.3のamb評価器に関しての簡単な説明

問題4.50

分岐を左から右ではなく，ランダムに探す他はambと同じである，新しい特殊形式rambを実装せよ

ここで，そもそも分岐の候補はどこで作られているかが問題になる．
いままでいまいち動きがわからなかったけど，少しわかったので，自分用にメモ.

簡単のため

(amb 1 2 3 4 5)

の動きに関して説明する．
必要になる関数は以下のもの

(define (analyze exp)
  (cond [(self-evaluating? exp)
         (analyze-self-evaluating exp)]
　　　　　　　　:
        [(amb? exp) (analyze-amb exp)]
                          :
        [else
         (error "Unknown expression type -- ANALYZE" exp)]))

(define (amb? exp) (tagged-list? exp 'amb))

(define (amb-choices exp) (cdr exp))

(define (ambeval exp env succeed fail)
  ((analyze exp) env succeed fail))

(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))))

(define (analyze-self-evaluating exp)
  (lambda (env succeed fail)
    (succeed exp fail)))

(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 success
                     (lambda (val next-alternative)
                       (announce-output output-prompt)
                       (user-print val)
                       (internal-loop next-alternative))
                     ;; ambeval failuer
                     (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))))

説明

driver-loopが起動している状態で，(amb 1 2 3 4 5)をamb評価器に食わせると，
inputに(amb 1 2 3 4 5)が代入され，これはtry-againではないので，ambevalが呼び出される．
ambevalの各引数には，

exp = (amb 1 2 3 4 5)
env = the-global-environment
succeed = (lambda (val next-alternative)
                               (announce-output output-prompt)
                               (user-print val)
                               (internal-loop next-alternative))

fail = (lambda ()
                       (announce-output
                        ";;; There are no more values of ")
                       (user-print input)
                       (driver-loop)))))))

が入る．(analyze exp)により，analyze-ambが呼び出される． (let ((cprocs (map analyze (amb-choices exp))))により，expの引数が，(map analyze)され，cprocsに入る．この時点で，cprocsには，

#<closure (analyze-self-evaluating analyze-self-evaluating)>

のリストが入っている．その後

(lambda (env succeed fail)
      (define (try-next choices)
        (if (null? choices)
            (fail)
            ((car choices) env
                                  succeed
                                  (lambda ()
                                  (try-next (cdr choices))))))

により，env, succeed, failを引数とするclosureが定義される．これが(analyze exp)の結果である．そして，ambevalに戻り，このclosureにenv,succeed,failが代入される．
ここで重要なのが，上記try-nextである.これは，演算子に(car choices), 被演算子に，ambevalに渡されたenv, succeed，lambda式を取る．
それぞれは，以下のようになっている．

(car choices) = #<closure (analyze-self-evaluating analyze-self-evaluating)>
env = the-global-environment
succeed = (lambda (val next-alternative)
                               (announce-output output-prompt)
                               (user-print val)
                               (internal-loop next-alternative))
lambda式 = (lambda () try-next (cdr choices))

ところで，analyze-self-evaluatingはexpを引数にとり，env, succeed,failを引数にとるclosureを返す．そのclosureの中身は，(succeed exp fail).
これをこの例題に即して展開すると，

(succeed exp fail)
      ↓
((lambda (val next-alternative)
               (announce-output output-prompt)
               (user-print val)
               (internal-loop next-alternative)))
   1                                                  ;val
   (lambda () try-next (cdr choices)) ;next-alternative
   )

すると，先頭のlambda式が実行され，(user-print 1)より，1が表示され，(internal-loop next-alternative)より，再び入力待ちの状態になる．
ここで，internal-loopの引数はtry-againとなる．この入力待ちの状態で，amb評価器にtry-againを食わせると，

(if (eq? input 'try-again)
          (try-again)

より，先ほど保存したnext-alternative, つまり，(lambda () try-next (cdr choices))が実行され，2が表示される．
try-againの度に，next-alternativeが呼び出され，最終的にchoicesがnullになる．nullになると，analyze-ambに渡されたfail, つまり，

fail = (lambda ()
                       (announce-output
                        ";;; There are no more values of ")
                       (user-print input)
                       (driver-loop)))))))

が実行され，";;; There are no more values of "がamb評価器に表示される．そして，(user-print input)により，もとの式自体表示され, 再び(driver-loop)が実行されて，
入力待ち状態になる．

これはまさに継続の動きで，どこに飛ぶかを引数として維持しながら，計算をしていく．そのため成功継続，失敗継続という言葉が使われる．

分岐の順序は(amb-choices)が作り出すので，例えば右から左に分岐を作りたい場合，以下のどれでもできる．

(define (amb-choices exp) (reverse (cdr exp)))
(let ((cprocs (map analyze (reverse (amb-choices exp)))))
(let ((cprocs (reverse (map analyze (amb-choices exp)))))

amb-choicesがまさに分岐選択なので，1番がいいと思う．

さかもとのブログ

つらつらと

SICP4.3のamb評価器に関しての簡単な説明

説明