読者です 読者をやめる 読者になる 読者になる

(wat-aro)

無職から有職者にランクアップしました

SICP 問題 5.50

scheme SICP

4.1節の超循環評価器を5.5で作った翻訳系でコンパイルする.
 

問題5.50 – SICP(計算機プログラムの構造と解釈)その302 : Serendip - Webデザイン・プログラミング

http://himoiku.cocolog-nifty.com/blog/2008/07/sicp550_f385.html

ここを参考にしました.
まずここに書いてるmapがバグるっていうのがわからないところからスタート.
エラーメッセージを見ても原因がmapだとは気づかず,
この2つのブログを参考にしながら修正するも,翻訳系がダメなのかインタプリタがダメなのかもなかなかわからず.
 
三日間いろいろなバグに出会いながら最後まで残ったのが2つ.
一つ目はどこかで環境の保護がされていないために,再帰のベースケースから戻ってきても環境が回復されずその後の計算がおかしくなるバグ.
二つ目はレキシカルアドレッシングで翻訳時環境から得たアドレスが狂うバグ.
一つ目は最終的にソースをenvで検索してpreservingまたはmake-instruction-sequenceでenvが足らないところがないか探しました.
レキシカルアドレッシングの実装時に,作ったcompile-variablesとcompile-assignmentのmake-instruction-sequenceのneededにenvが入っていないためでした. 二つ目の原因は内部定義でした.
翻訳時環境が拡張されるのはcompile-lambda-bodyだけなので,内部定義でフレームが拡張されず,
find-variableが指すアドレスがこのシンボルがない時の環境でのアドレスなので実行時環境では違うものを指してしまいバグっていました.
これの解決策として,scan-out-definesでmake-letを使い内部定義を全てletに吐き出し,
それをlet->combinationでlambdaに変換することで解決しました.
根本的な解決ではないですが,とりあえず,コンパイルについては問題なく動きます.
 
以下はテスト. 翻訳系のREPLのEC-COMPからdriver-loopを呼び出し,
翻訳系でコンパイルしたインタプリタのREPL,MC-Evalに入っています.

;;;EC-COMP input:
(driver-loop)


;;; MC-Eval input:
(define (map proc lst)
  (if (null? lst)
      '()
      (cons (proc (car lst))
            (map proc (cdr lst)))))

;;; MC-Eval value:
ok

;;; MC-Eval input:
(map car '((1 2) (3 4) (5 6)))

;;; MC-Eval value:
(1 3 5)

;;; MC-Eval input:
(define (fact n)
  (let iter ((count 1) (product 1))
    (if (< n count)
        product
        (iter (+ 1 count) (* count product)))))

;;; MC-Eval value:
ok

;;; MC-Eval input:
(fact 5)

;;; MC-Eval value:
120

;;; MC-Eval input:
(define (factorial n)
  (if (< n 2)
      n
      (* (factorial (- n 1))
         n)))

;;; MC-Eval value:
ok

;;; MC-Eval input:
(factorial 5)

;;; MC-Eval value:
120

;;; MC-Eval input:
(define (fact n)
  (define (iter count product)
    (if (< n count)
        product
        (iter (+ 1 count) (* count product))))
  (iter 1 1))

;;; MC-Eval value:
ok

;;; MC-Eval input:
(fact 5)

;;; MC-Eval value:
120