« SICP 4.1.7 Separating Syntactic Analysis from Execution | Main | 良い翻訳本 »

2007.09.11

4.3 Variations on a Scheme -- Nondeterministic Computing

(amb 1 2 3)がやっていること

driver-loop

ambeval

analyze exp

analyze-amb
 ↓
 amb-choices でambの引数が変わる
 ↓
 cprocsには、ambの引数を返す手続きが入る。1を返す手続き、2を返す手続き、3を返す手続き。
 ↓
 analyze-ambは、cprocの先頭を評価して、trueならsucceedを実行し、falseなら次の引数を評価する関数を返す。次が無い場合、(null? cproc)、failを実行する。failとsucceedは、引数として与えられる。

ambevalに戻って、analyzeで戻ってきた手続きを実行する。((analyze exp) env succeed fail))
driver-loopの場合、それぞれ成功した場合、失敗した場合のメッセージを表示している。

教科書読まずに想像だけど、この手続きが状態を保持しているのね。所々に、continuationという文字が出ている。継続のpureな姿がここにありそうだ。

(list (amb 1 2 3) (amb 'a 'b))の場合、analyzeされると、1 2 3を作る手続きと、'a 'bを作る手続きの両方が式全体のanalyzeの結果として保存され、順に呼び出される。なるほど。だから、新しくトップレベルでamb式を使うと、driver-loopが持っている手続きが新しい手続きで上書きされてしまう。結果的に次の問題に行くけど、前回の問題の結果は消えてしまう。

写経して、letのanalyze手続きを加えると、prime-sum-pair動いた。
(define (analyze-let exp)
(analyze (let->combination exp)))

分かったこと
・requireの無いambはただの総当たりジェネレータ。
・処理系を作るって事は、与えられた問題の一般解とユーザーインターフェイスを作るって事

|

« SICP 4.1.7 Separating Syntactic Analysis from Execution | Main | 良い翻訳本 »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/16411679

Listed below are links to weblogs that reference 4.3 Variations on a Scheme -- Nondeterministic Computing:

« SICP 4.1.7 Separating Syntactic Analysis from Execution | Main | 良い翻訳本 »