問題4.22-4.24 - nrvctの日記

何か今使ってる椅子が座る度に部品がぽろって欠けてくんですけど寿命なんでしょうか。どうでもいいですね。

構文解析を分離して、超循環評価機の効率を上げるみたいです。SICPのコードをそのまま移すとなぜかscan-out-definesでエラーになります。たぶんanalyze-sequenceで式の並びをlambdaの並びにしてるからだと思われます。なので、今回もscan-out-definesを使えるように、次のように変更します。
まず、make-procedureからscan-out-definesを外します。次に、analyze-sequenceを次のように変更します。

(define (analyze-sequence exps)
  (define (sequentially proc1 proc2)
    (lambda (env) (proc1 env) (proc2 env)))
  (define (loop first-proc rest-procs)
    (if (null? rest-procs)
        first-proc
        (loop (sequentially first-proc (car rest-procs))
              (cdr rest-procs))))
  (let* ((trans-exps (scan-out-defines exps))
         (procs (map analyze trans-exps)))
    (if (null? procs)
        (error "Empty sequence -- ANALYZE"))
    (loop (car procs) (cdr procs))))

変更箇所はletをlet*にしてexpsを同時有効範囲則を満たす変換を施したものをtrans-expsに束縛し、expsの代わりにtrans-expsにanalyzeを作用させるという点のみです。これで同時有効範囲則をみたせます。letを作ってから確認してみます。

4.22

letを追加します。analyzeに次を挿れればいいだけです。

...
((let? exp) (analyze (let->combination exp)))
...

これで、問題4.19の式の評価がどうなるか見てみます。

;;; M-Eval input:
(let ((a 1))
  (define (f x)
    (define b (+ a x))
    (define a 5)
    (+ a b))
  (f 10))
unbound -- LOOKUP-VARIABLE-VALUE : a

同時有効範囲則を満たしていることが確認できました。

4.23

Alyssaの作ったものは、なんていうか式の並びを評価する手続きではなくて、式の並びを評価した結果を返していると思う。これはprocsが基盤Schemeのlambdaで、つまりenvを与えれば実行できる手続きとして表現されているから。
もとのやつは、ちゃんとenvを与えれば上から順に評価するlambdaを返してくれる。
結果は変わらないんだと思うけど(いや変わる場合もあるかも)、構文解析を分離しているつもりなのに評価をしちゃったらなんかダメだと思うので、Alyssaのは適切ではない。
上手く書けないな。

4.24

timeを超循環評価器に組み込もうとしたのですが、timeって特殊形式なんですね。無理でした。なので次のようにして時間比較してみます。
まず、構文解析を分離していない評価器。

> (time
   (eval '((lambda ()
             (define (fib n)
               (cond ((= n 0) 0)
                     ((= n 1) 1)
                     (else (+ (fib (- n 1)) (fib (- n 2))))))
             (fib 20)))
         the-global-environment))
cpu time: 11373 real time: 11379 gc time: 108
6765
> (time
   (eval '((lambda ()
             (define (fib n)
               (cond ((= n 0) 0)
                     ((= n 1) 1)
                     (else (+ (fib (- n 1)) (fib (- n 2))))))
             (fib 21)))
         the-global-environment))
cpu time: 18157 real time: 18157 gc time: 104
10946

次に構文解析を分離した評価器。

> (time
   (eval '((lambda ()
             (define (fib n)
               (cond ((= n 0) 0)
                     ((= n 1) 1)
                     (else (+ (fib (- n 1)) (fib (- n 2))))))
             (fib 20)))
         the-global-environment))
cpu time: 4901 real time: 4902 gc time: 116
6765
> (time
   (eval '((lambda ()
             (define (fib n)
               (cond ((= n 0) 0)
                     ((= n 1) 1)
                     (else (+ (fib (- n 1)) (fib (- n 2))))))
             (fib 21)))
         the-global-environment))
cpu time: 7812 real time: 7819 gc time: 108
10946

結構構文解析が重たいようですね。割合は省略。ただ、問題3.57で、(fib n)の加算回数a_nを求めているので、これを使えばなんとか出せそうです。でもやりません。

区切りがいいので、ここで一旦とめます。