SICP 4.1.7 Separating Syntactic Analysis from Execution

ノート

我々の評価器は評価しながら実行し、評価した結果は残っていないので再帰であっても同じ式であっても何度でも評価するので非効率。
analyzeの結果として実行部としてベースのLispの手続きを返してenvの元で実行する。

analyze-sequenceはちょっと複雑。
シーケンス内の各式をmapでanalyzeして返って来た手続きのリストをprocsに保存。
loopはprocsが無くなるまでsequentiallyにfirst-procと(car rest-procs)つまり２番目の手続きを纏めさせて、纏めた手続きを次のloopのfirst-procとして再帰。
最初にsequentiallyで纏めるのは最初の手続きと２番目の手続き。
次にsequentiallyが纏めるのは、最初と２番目の手続きを纏めた手続きと、３番目の手続き。
その次にsequentiallyが纏めるのは、最初〜３番目の手続きを纏めた手続きと、４番目の手続き。
と言った具合。
最終的に全部纏まった手続きが返る。
テキストのコードは最後のifに対するelse部が無いが、loopを呼び出す部分が実質else。何故このコードにしたのかは少し不思議。

scan-out-definitionsはcontentsとして元のLispコードを期待していたが、analyze-lambdaでベースLispの手続きに直したリストが渡って来てしまうのでもう使えない。make-procedureは元に戻す。

initial-envにnullも追加して動作確認。

> (eval '(define (f x)
           ((lambda (even? odd?)
              (even? even? odd? x))
            (lambda (ev? od? n)
              (if (= n 0) true (od? ev? od? (- n 1))))
            (lambda (ev? od? n)
              (if (= n 0) false (ev? ev? od? (- n 1))))))
        the-global-environment)
'ok
> (eval '(define (filter pred lst)
           (cond ((null? lst) null)
                 ((pred (car lst)) (cons (car lst) (filter pred (cdr lst))))
                 (else (filter pred (cdr lst)))))
      the-global-environment)

'ok
> (eval '(filter f '(0 1 2 3 4 5 6 7 8 9 10)) the-global-environment)
'(0 2 4 6 8 10)
> 

Exercise 4.22

特別な事は何も無し。

(define (analyze exp)
  (cond ((self-evaluating? exp) 
;…中略
        ((let? exp) (analyze (let->combination exp)))
;…以下省略

; 以下は以前のExerciseのまま
(define (let? exp) (tagged-list? exp 'let))
(define (let-variables exp) (cadr exp))
(define (let-body exp) (cddr exp))
(define (let-parameters variables) (map car variables))
(define (let-arguments variables) (map cadr variables))
(define (let->combination exp)
  (if (named-let? exp)
      (expand-named-let exp)
      (cons (make-lambda (let-parameters (let-variables exp))
                         (let-body exp))
            (let-arguments (let-variables exp)))))

(define (named-let? exp) (symbol? (named-let-name exp)))
(define (named-let-name exp) (cadr exp))
(define (named-let-variables exp) (caddr exp))
(define (named-let-body exp) (cdddr exp))
(define (expand-named-let exp)
  (sequence->exp (list (cons 'define
                             (cons (cons (named-let-name exp)
                                         (let-parameters (named-let-variables exp)))
                                   (named-let-body exp)))
                       (cons (named-let-name exp)
                             (let-arguments (named-let-variables exp))))))

動作確認

> (eval '(define (f x)
           (let ((even? (quote *unassigned))
                 (odd? (quote *unassigned)))
             (set! even? (lambda (n)
                           (if (= n 0)
                               true
                               (odd? (- n 1)))))
             (set! odd? (lambda (n)
                          (if (= n 0)
                              false
                              (even? (- n 1)))))
             (even? x)))
        the-global-environment)
'ok
> (eval '(define (filter pred lst)
           (cond ((null? lst) null)
                 ((pred (car lst)) (cons (car lst) (filter pred (cdr lst))))
                 (else (filter pred (cdr lst)))))
        the-global-environment)

'ok
> (eval '(filter f '(0 1 2 3 4 5 6 7 8 9 10)) the-global-environment)
'(0 2 4 6 8 10)
> (eval '(define (fib n)
           (let fib-iter ((a 1)
                          (b 0)
                          (count n))
             (if (= count 0)
                 b
                 (fib-iter (+ a b) a (- count 1)))))
        the-global-environment)
'ok
> (eval '(fib 10) the-global-environment)
55
> 

Exercise 4.23

テキストのanalyze-sequenceはシーケンス内の式の数-1個の（無名）手続きを作る一方、Alyssaの方はこれがexecute-sequenceに相当すると考えると、リソースと言う面ではAlyssaの方が良いと言えなくもない。テキストの方はクロージャの塊を持ち、また再帰ではないので呼び出しの数だけフレームを作るが、execute-sequenceは一応末尾再帰になっているのであまりリソースは食わない筈。

テキストの方法は実行時に条件分岐は一切無い（積まれた手続きが無くなったら終わり）が、Alyssaのexecute-sequenceは毎回(null? (cdr procs))を呼ぶ、つまりどこがシーケンスの終わりなのかの解析が実行時まで持ち越されているのでパフォーマンスの面ではAlyssaの方が不利。

Exercise 4.24

Racketの(current-inexact-milliseconds)を使ってevalの前後で時間差を測る。
元の実装

> (current-inexact-milliseconds)
1375099573631.486
> (let ((start (current-inexact-milliseconds)))
    (eval '(fib 10000) the-global-environment)
    (- (current-inexact-milliseconds) start))
6786.22412109375
> (let ((start (current-inexact-milliseconds)))
    (eval '(fib 10000) the-global-environment)
    (- (current-inexact-milliseconds) start))
6881.777099609375
> (let ((start (current-inexact-milliseconds)))
    (eval '(fib 10000) the-global-environment)
    (- (current-inexact-milliseconds) start))
7262.031982421875
> 

凡そ７秒前後掛かっている。
analyzeを分離した実装。

> (let ((start (current-inexact-milliseconds)))
    (eval '(fib 10000) the-global-environment)
    (- (current-inexact-milliseconds) start))
3091.47607421875
> (let ((start (current-inexact-milliseconds)))
    (eval '(fib 10000) the-global-environment)
    (- (current-inexact-milliseconds) start))
3082.43994140625
> (let ((start (current-inexact-milliseconds)))
    (eval '(fib 10000) the-global-environment)
    (- (current-inexact-milliseconds) start))
2989.8759765625
> 

３秒前後。
ちょっとこの結果だけで２倍強掛かっているとは言えないが、実のところ簡単な実行であればその差は感じない。