SICP読書会

1月29日 SICP読書会議事録

問題5.26

n total-pushes max-depth
1 64 10
2 99 10
3 134 10
4 169 10
5 204 10
6 239 10
7 274 10
8 309 10
9 344 10
10 379 10

a: 最大深さは10で固定。

b: n*35+29

問題5.27

n total-pushes max-depth
1 16 8
2 48 13
3 80 18
4 112 23
5 144 28
6 176 33
7 208 38
8 240 43
9 272 48
10 304 53

プッシュ回数 = n*32-16

最大深さ = n * 5 + 3

問題5.28

P332のev-sequence〜ev-sequence-last-expのコードを P333のev-sequence〜ev-sequence-endのコードに置き換え.

n total-pushes(5.26) max-depth(5.26) total-pushes(5.27) max-depth(5.27)
1 70 17 18 11
2 107 20 52 19
3 144 23 86 27
4 181 26 120 35
5 218 29 154 43
6 255 32 188 51
7 292 35 222 59
8 329 38 256 67
9 366 41 290 75
10 403 44 324 83

左から プッシュ回数 = 37 * n + 33
最大深さ = 3 * n + 14
プッシュ回数 = 34 * n - 16
最大深さ = 8 * n + 3

問題5.29

a.

n total-pushes max-depth Fib(n)
2 72 13 1
3 128 18 2
4 240 23 3
5 408 28 5
6 688 33 8
7 1136 38 13

D(n)=5*n + 3

b.

  • S(n)=S(n-1)+S(n-2)+40
  • S(n)=56*Fib(n+1)-40

問題5.30

a. lookup-variable の (error "Unbound Variable") を、束縛されていない変数を表わす値を返すようにする。 

(define *unbound-variable* (list 'unbound))

(define (lookup-variable-value var env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (car vals))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        *unbound-variable* ;(error "Unbound variable")
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

(define (unbound-value? val)
  (eq? val *unbound-variable*))

eceval では、unbound-value かをチェックして、もしそうなら signal-error に 分岐する。 

ev-variable
  (assign val (op lookup-variable-value) (reg exp) (reg env))
  (test (op unbound-value?) (reg val))
  (branch (label unbound-variable))
  (goto (reg continue))

unbound-variable
  (assign val (const unbound-variable-error))
  (goto (label signal-error))

signal-error
  (perform (op user-print) (reg val))
  (goto (label read-eval-print-loop))

b.

a. と同様に、プリミティブ関数がエラー値を返すようにして、 primitive-apply でエラーの値かをチェックする。 signal-error に渡す名前は、分岐をしてエラーの種類ごとにチェックしてもよかったが、面倒なのでエラーの値の car を取るようにした。（手抜き） 

(define *type-error* (list 'type-error))
(define *zero-division-error* (list 'zero-divison-error))

(define (error-value? val)
  (or
    (eq? val *type-error*)
    (eq? val *zero-division-error*)
    ))

(define primitive-procedures
  (list (list 'car (lambda (x) (if (pair? x) (car x) *type-error*)))
        (list 'cdr (lambda (x) (if (pair? x) (cdr x) *type-error*)))
        <omit>
        (list '/ (lambda (a b) (if (zero? b) *zero-division-error* (/ a b))))
        <omit>
        ))

(define eceval-operations
  (list
   <omit>
   (list 'error-value-name car)
   <omit>
   )

primitive-error
  (assign val (op error-value-name) (reg val))
  (goto (label signal-error))

signal-error
  (perform (op user-print) (reg val))
  (goto (label read-eval-print-loop))

primitive-apply
  (assign val (op apply-primitive-procedure)
              (reg proc)
              (reg argl))
  (test (op error-value?) (reg val))
  (branch (label primitive-error))
  (restore continue)
  (goto (reg continue))

問題5.31

各項と、save,restore を評価順に書き、不要なものをコメントアウトして書く。 

(f 'x 'y)

;(save env)
f
;(restore env)
;(save proc)
;(save argl)
;(save env)
'x
;(restore env)
;(restore argl)
;(save argl)
'y
;(restore argl)
;(restore proc)

((f) 'x 'y)

(save env)
(f)
(restore env)
;(save proc)
;(save argl)
;(save env)
'x
;(restore env)
;(restore argl)
;(save argl)
'y
;(restore argl)
;(restore proc)

(f (g 'x) y)

;(save env)
f
;(restore env)
(save proc)
(save argl)
(save env)
(g 'x)
(restore env)
(restore argl)
;(save argl)
y
;(restore argl)
(restore proc)

(f (g 'x) 'y)

;(save env)
f
;(restore env)
(save proc)
(save argl)
;(save env)
(g 'x)
;(restore env)
(restore argl)
;(save argl)
y
;(restore argl)
(restore proc)

preserving はどう使われるか現時点で予想。 例えば問題文によると、被演算子列の前後では proc を退避回復しなければならない。

そのため、被演算子列をコンパイルした命令列までコンパイルし、それを前後の命令列と組合わせる。被演算子列の命令列が seq1 として preserving されるとき、proc は退避回復しなければならない。そこで、preserving の呼出しは次のようになるだろう。 

(preserving '(proc) <<被演算子列の命令列>> <<後に続く命令列>>)

このような操作を再帰的に行うのだろう。

この予想を元に、上の余分な退避回復を preserving によって除けるかを考えると、全て取り除けるように思う。

問題 5.32

a.

eval-dispatch で、application? と別に simple-application? を加え、別のルーチンに飛ぶようにした。 

  (test (op simple-application?) (reg exp))
  (branch (label ev-simple-application))
  (test (op application?) (reg exp))
  (branch (label ev-application))

ev-simple-application は、演算子を評価するときに env を退避回復しない。 また、演算子の評価のために eval-dispatch ではなく ev-variable に直接飛んでいる。（演算子がシンボルであることはあらかじめわかっているので）

ev-appl-operand-loop 以下については ev-application と同じなので、そちらに無条件ジャンプすれば済む。 

ev-simple-application
  (save continue)
  (assign unev (op operands) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))
  (assign continue (label ev-simp-appl-did-operator))
  (goto (label ev-variable))
ev-simp-appl-did-operator
  (restore unev)
  (assign argl (op empty-arglist))
  (assign proc (reg val))
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))
  (save proc)
  (goto (label ev-appl-operand-loop))

b.

作るの大変そう。 --- 日下部

最適化可能な条件を増やしていくと、それを毎回分岐させるロジックが毎回走ることにならないか。 --- 伊東

コードがぐちゃぐちゃになっちゃいそう。苦労の割に。 --- 柴田

実行時にやることじゃないよね。 --- ささだ

わからないです。 --- 須賀

条件が多くなって保守が不可能になりそう。 --- 平田

場合によっては最適化にかかる時間の方が実行速度の短縮よりも上まわってしまう。 ---久井

大域的な最適化に対応できない。 --- 久井

Created: 2006-01-28 08:30:30(+0900) by tahara
Modified: 2006-01-29 17:19:59(+0900) by ひらっち

Powered by Kahua