amb評価器の動かし方(DrScheme v4.1対応版)
先日より素人くさいSICP 読書会(http://www.csus4.net/hiki/SICPReading/)におじゃまさせていただいています。
加わったのがだいぶ途中の段階からだったため（問題4.36から）、先ずは話についていくためにきちんとamb 評価器が実行できる環境を手に入れたいと思っていました。
当たり前ですが、動かせる環境が手元にあると理解度がぜんぜん違うんですよね。
今日までに何度か試していたのですが、一見動いているようでいざ演習問題をやろうとするとエラーになったり、訳のわからないハマりどころがあり、役に立っていませんでした。
今日は時間を取っていろいろ試行錯誤し、動かせるところまでで来たので報告してみます。
先ず、amb 評価器のソースを入手し、DrScheme 用に加工
http://mitpress.mit.edu/sicp/code/index.html
から、
- ch4-ambeval.scm
- ch4-mceval.scm
を。また、SICPに掲載されているコード断片の詰まった
- ch4.scm
をダウンロードしてください。
次にch4-ambeval.scm のファイルの先頭に以下を追加して下さい。(入れる場所は適当でいいです)
(define (error message) message) (define true #t) (define false #f)
またR5RSでは、eval とapply の定義を上書きできないようになっているようなので（エラーになる）、これらの関数を他の名前に置き換える必要があります。
よってch4-mceval.scm 内のeval とapply をそれぞれmyeval, myapply 等と置換して下さい。
※"eval-何とか" や、"apply-何とか" があるので、盲目的に全部置換しちゃいけません！大丈夫、そんなに数はないから。
ここ、ちょっと面倒ですよね〜。
DrScheme をインストールして起動
起動したら、用意していたch4-ambeval.scm を読み込んでおいて下さい。
言語はR5RS を選択
DrScheme は、ひとつのScheme 実装でなく、いくつかの言語を選択できるようになっています。
以前は"Essentials of Programming Languages(2nd ed.)" を選べば動いたように思いますが、
Version 4.1では"Essentials of Programming Languages(3nd ed.)" になっており、
これでは動かないので別の言語を選択する必要がありました。
ただ、その他の言語をいろいろ試してみたのですが「set-car! が無い」等と怒られてしまいます。
DrScheme の[ヘルプ]-[ヘルプデスク]から、set-car! で検索して確かめると、R5RS に存在していることがわかりました。
よって、R5RSしかないのだと思います。R5RS を選んでください。
（R5RSでもうまく動かなかった部分は泥臭く調整しましたが、それが上に述べたファイルの改変の内容でした。）
DrScheme の実行ボタンを押す
ようこそ DrScheme, バージョン 4.1 [3m]. 言語: R5RS; memory limit: 128 megabytes. metacircular-evaluator-loaded amb-evaluator-loaded
のように表示されればOK.
そして以下を打ち込んで実行し、手動でamb 評価器を起動します。
;; この２ステップでamb 評価器が起動 (define the-global-environment (setup-environment)) (driver-loop)
この段階でamb 評価器が起動しています。
続いて以下のコードを試してみてください。
;; amb 評価器内で実行 (define (require p) (if (not p) (amb))) (define (an-element-of items) (require (not (null? items))) (amb (car items) (an-element-of (cdr items)))) (an-element-of '(1 2 3))
結果として1が表示されれば動いています。
更なる動作確認のため、SECTION 4.3.2 -- Logic Puzzles も動かしてみましょう。
ch4.scm から関数require、distinct? およびmultiple-dwelling をamb 評価機内にコピペして、
その上で(multiple-dwelling) とすると実行が確認できます。
具体的には以下のようなコマンド行になるでしょう。
;;; Amb-Eval input: (define (require p) (if (not p) (amb))) (define (distinct? items) (cond ((null? items) true) ((null? (cdr items)) true) ((member (car items) (cdr items)) false) (else (distinct? (cdr items))))) (define (multiple-dwelling) (let ((baker (amb 1 2 3 4 5)) (cooper (amb 1 2 3 4 5)) (fletcher (amb 1 2 3 4 5)) (miller (amb 1 2 3 4 5)) (smith (amb 1 2 3 4 5))) (require (distinct? (list baker cooper fletcher miller smith))) (require (not (= baker 5))) (require (not (= cooper 1))) (require (not (= fletcher 5))) (require (not (= fletcher 1))) (require (> miller cooper)) (require (not (= (abs (- smith fletcher)) 1))) (require (not (= (abs (- fletcher cooper)) 1))) (list (list 'baker baker) (list 'cooper cooper) (list 'fletcher fletcher) (list 'miller miller) (list 'smith smith)))) ;;; Starting a new problem ;;; Amb-Eval value: ok ;;; Amb-Eval input: ;;; Starting a new problem ;;; Amb-Eval value: ok ;;; Amb-Eval input: (multiple-dwelling) ;; ここで実行 ;;; Starting a new problem ;;; Amb-Eval value: ((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
SICPにある通りの答えが出ていますので、きちんと動いていますね。
