SICP 読み (228) 4.3.3 amb 評価器の実装

SICP scheme

直前エントリは微妙に中途半端だな。(list (amb 1 2 3)) とか (list (amb 1 2 3) (amb 4 5 6)) などがどのように取り扱われるか、についてざくっとマトメておきます。

(list (amb 1 2 3))

まず、analyze-application にて list が analyze されて

(lambda (env succeed fail)
  (succeed (lookup-variable-value list env) fail))

が pproc にセット。又、引数リストが map analyze されて直前エントリにもある

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

がリストになって aprocs にセットされるのか。で (lambda (env succeed fail) 略) な手続きを戻します、と。この手続きが例示されている評価器で実行されるとして (成功な継続と失敗な継続が例示されているものとして) 実際の流れを見てみると、pproc な手続きを the-global-environment と

(lambda (proc fail2)
  (get-args aprocs
	    env
	    (lambda (args fail3)
	      (execute-application proc args succeed fail3))
	    fail2))

な成功継続と評価器からもらってきた失敗継続を渡して実行。ちなみに上記の成功な継続は get-args の最初の呼び出しから正常に戻った時に実行される形になる。最初の get-args では、(amb 1 2 3) が戻した手続きを

(lambda (arg fail2)
  (get-args (cdr aprocs)
	    env
	    (lambda (args fail3)
	      (succeed (cons arg args) fail3))
	    fail2))

な手続きを成功な継続として呼び出す。ってココまで書いたんですがさらに整理が必要やっさ。とりあえず、get-args 一発目では具体的には以下の手続きになるはず。

((lambda (arg fail2)
   (get-args (cdr apeocs) env (lambda (args fail3) 
				(succeed (cons arg args) fail3)) fail2))
 1 
 (lambda () (try-next (cdr '((lambda (env succeed fail)
			       (succeed 2 fail))
			     (lambda (env succeed fail)
			       (succeed 3 fail)))))))

なんか名前のソレ的に非常に微妙です。基本的なイメージとしては aproc の成功継続でリストを cdr していって aprocs が '() になった時点で get-args の成功継続をたぐって execute-application を呼び出す継続に戻るカンジ、と言えば良いか。
もう少し aprocs が null になって時点から整理すると、

  • (succeed '() fail) が呼ばれる。成功継続の中で succeed を読んでいますが、これが読み解くなかでイメージに苦しむ所以かな、と。ちなみに fail には amb の失敗継続がセットされている (lambda () (try-next (cdr choices))) みたいなソレ。
  • args に '() と失敗継続がセットされてて、arg は (amb 1 2 3) の一発目が戻す 1 がセット済み。なので (1) と件の失敗継続を一番最初の succeed に渡す。
  • execute-application に引数で渡された args と失敗継続をセット。こいつに渡す succeed は大域な成功継続。

(list (amb 1 2 3) (amb 4 5 6))

ぢつはこのケイスでの末端要素な amb が fail を呼ぶ時の挙動がイメージできていませんでした。分かりにくいかもしれませんが、ざくっと控えを。

  • 最初に get-args の中で処理対象となるのは (amb 1 2 3)。この手続きの成功継続には 1 と (try-next (cdr choices)) が渡される (choices は (2 3))。ちなみにこの成功継続に渡される失敗継続 (って微妙な表現だなぁ) にセットされた (try-next (cdr choices)) な手続きオブジェクトに設定されている fail は大域の失敗継続
  • 次の get-args では (amb 4 5 6) が処理対象。この手続きの成功継続には 4 と (try-next (cdr choices)) が渡される (choices は (5 6))。ここで成功継続に渡されている失敗な継続の手続きオブジェクトは何か、というのがポイント
  • 最初の (amb 1 2 3) に渡される fail は大域の失敗継続
  • 次の (amb 4 5 6) に渡される fail は (amb 1 2 3) の残り

どんな形で_その前の失敗継続_を覚えてるのか謎、だったんですが手続きオブジェクト、というのがカギでした。こんなソレを自分で作れ、と言われても絶対無理だな。

ひと通り確認できたのできちんと試験が書ける状態になっているはずなんですが、どこまでヤレるか微妙な週末ッス。

もう少し

  • 失敗継続は基本的に持ち回る
  • 新たな選択が追加される時、その手続きオブジェクトの fail に直前の失敗継続がセットされるので、バックトラックが可能になっている

まだまだ読む事も微妙だし、それ以上に書くという部分では (以下略