Serendip

Web Studio

問題5.11 a.

afterfib-n-2 の内容を次のように変更できる。

afterfib-n-2
  (assign n (reg val))
  (restore val)
  ...
↓
afterfib-n-2
  (restore n)
  ...

問題5.6のように (fib 4) として、スタックの処理内容を書き出してみる。

                                            ; [n] [val] [continue] [stack]
(test (op <) (reg n) (const 2))             ; [n:4] [val:] [continue:fib-done] [stack:()] (< 4 2) => false
(save continue)                             ; [n:4] [val:] [continue:fib-done] [stack:(fib-done)]
(assign continue (label afterfib-n-1))      ; [n:4] [val:] [continue:afterfib-n-1] [stack:(fib-done)]
(save n)                                    ; [n:4] [val:] [continue:afterfib-n-1] [stack:(4 fib-done)]
(assign n (op -) (reg n) (const 1))         ; [n:3] [val:] [continue:afterfib-n-1] [stack:(4 fib-done)]
(goto (label fib-loop))                     ; goto fib-loop
(test (op <) (reg n) (const 2))             ; (< 3 2) => false
(save continue)                             ; [n:3] [val:] [continue:afterfib-n-1] [stack:(afterfib-n-1 4 fib-done)]
(assign continue (label afterfib-n-1))      ; [n:3] [val:] [continue:afterfib-n-1] [stack:(afterfib-n-1 4 fib-done)]
(save n)                                    ; [n:3] [val:] [continue:afterfib-n-1] [stack:(3 afterfib-n-1 4 fib-done)]
(assign n (op -) (reg n) (const 1))         ; [n:2] [val:] [continue:afterfib-n-1] [stack:(3 afterfib-n-1 4 fib-done)]
(goto (label fib-loop))                     ; goto fib-loop
(test (op <) (reg n) (const 2))             ; (< 2 2) => false
(save continue)                             ; [n:2] [val:] [continue:afterfib-n-1] [stack:(afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(save n)                                    ; [n:2] [val:] [continue:afterfib-n-1] [stack:(2 afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(assign n (op -) (reg n) (const 1))         ; [n:1] [val:] [continue:afterfib-n-1] [stack:(2 afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(goto (label fib-loop))                     ; goto fib-loop
(test (op <) (reg n) (const 2))             ; (< 1 2) => true => goto immediate-answer
(assign val (reg n))                        ; [n:1] [val:1] [continue:afterfib-n-1] [stack:(2 afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(goto (reg continue))                       ; goto afterfib-n-1
(restore n)                                 ; [n:2] [val:1] [continue:afterfib-n-1] [stack:(afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(restore continue)                          ; [n:2] [val:1] [continue:afterfib-n-1] [stack:(3 afterfib-n-1 4 fib-done)]
(assign n (op -) (reg n) (const 2))         ; [n:0] [val:1] [continue:afterfib-n-1] [stack:(3 afterfib-n-1 4 fib-done)]
(save continue)                             ; [n:0] [val:1] [continue:afterfib-n-1] [stack:(afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(assign continue (label afterfib-n-2))      ; [n:0] [val:1] [continue:afterfib-n-2] [stack:(afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(save val)                                  ; [n:0] [val:1] [continue:afterfib-n-2] [stack:(1 afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(goto (label fib-loop))                     ; goto fib-loop
(test (op <) (reg n) (const 2))             ; (< 0 2) => true => goto immediate-answer
(assign val (reg n))                        ; [n:0] [val:0] [continue:afterfib-n-2] [stack:(1 afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(goto (reg continue))                       ; goto afterfib-n-2
(restore n)                                 ; [n:1] [val:0] [continue:afterfib-n-2] [stack:(afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(restore continue)                          ; [n:1] [val:0] [continue:afterfib-n-1] [stack:(3 afterfib-n-1 4 fib-done)]
(assign val (op +) (reg val) (reg n))       ; [n:1] [val:1] [continue:afterfib-n-1] [stack:(3 afterfib-n-1 4 fib-done)]
(goto (reg continue))                       ; goto afterfib-n-1
(restore n)                                 ; [n:3] [val:1] [continue:afterfib-n-1] [stack:(afterfib-n-1 4 fib-done)]
(restore continue)                          ; [n:3] [val:1] [continue:afterfib-n-1] [stack:(4 fib-done)]
(assign n (op -) (reg n) (const 2))         ; [n:1] [val:1] [continue:afterfib-n-1] [stack:(4 fib-done)]
(save continue)                             ; [n:1] [val:1] [continue:afterfib-n-1] [stack:(afterfib-n-1 4 fib-done)]
(assign continue (label afterfib-n-2))      ; [n:1] [val:1] [continue:afterfib-n-2] [stack:(afterfib-n-1 4 fib-done)]
(save val)                                  ; [n:1] [val:1] [continue:afterfib-n-2] [stack:(1 afterfib-n-1 4 fib-done)]
(goto (labe fib-loop))                      ; foto fib-loop
(test (op <) (reg n) (const 2))             ; (< 1 2) => true => goto immediate-answer
(assign val (reg n))                        ; [n:1] [val:1] [continue:afterfib-n-2] [stack:(1 afterfib-n-1 4 fib-done)]
(goto (reg continue))                       ; goto afterfib-n-2
(restore n)                                 ; [n:1] [val:1] [continue:afterfib-n-2] [stack:(afterfib-n-1 4 fib-done)]
(restore continue)                          ; [n:1] [val:1] [continue:afterfib-n-1] [stack:(4 fib-done)]
(assign val (op +) (reg val) (reg n))       ; [n:1] [val:2] [continue:afterfib-n-1] [stack:(4 fib-done)]
(goto (reg continue))                       ; goto afterfib-n-1
(restore n)                                 ; [n:4] [val:2] [continue:afterfib-n-1] [stack:(fib-done)]
(restore continue)                          ; [n:4] [val:2] [continue:fib-done] [stack:()]
(assign n (op -) (reg n) (const 2))         ; [n:2] [val:2] [continue:fib-done] [stack:()]
(save continue)                             ; [n:2] [val:2] [continue:fib-done] [stack:(fib-done)]
(assign continue (label afterfib-n-2))      ; [n:2] [val:2] [continue:afterfib-n-2] [stack:(fib-done)]
(save val)                                  ; [n:2] [val:2] [continue:afterfib-n-2] [stack:(2 fib-done)]
(goto (labe fib-loop))                      ; goto fib-loop
(test (op <) (reg n) (const 2))             ; (< 2 2) => false
(save continue)                             ; [n:2] [val:2] [continue:afterfib-n-2] [stack:(afterfib-n-2 2 fib-done)]
(assign continue (label afterfib-n-1))      ; [n:2] [val:2] [continue:afterfib-n-1] [stack:(afterfib-n-2 2 fib-done)]
(save n)                                    ; [n:2] [val:2] [continue:afterfib-n-1] [stack:(2 afterfib-n-2 2 fib-done)]
(assign n (op -) (reg n) (const 1))         ; [n:1] [val:2] [continue:afterfib-n-1] [stack:(2 afterfib-n-2 2 fib-done)]
(goto (label fib-loop))                     ; goto fib-loop
(test (op <) (reg n) (const 2))             ; (< 1 2) => true => goto immediate-answer
(assign val (reg n))                        ; [n:1] [val:1] [continue:afterfib-n-1] [stack:(2 afterfib-n-2 2 fib-done)]
(goto (reg continue))                       ; goto afterfib-n-1
(restore n)                                 ; [n:2] [val:1] [continue:afterfib-n-1] [stack:(afterfib-n-2 2 fib-done)]
(restore continue)                          ; [n:2] [val:1] [continue:afterfib-n-2] [stack:(2 fib-done)]
(assign n (op -) (reg n) (const 2))         ; [n:0] [val:1] [continue:afterfib-n-2] [stack:(2 fib-done)]
(save continue)                             ; [n:0] [val:1] [continue:afterfib-n-2] [stack:(afterfib-n-2 2 fib-done)]
(assign continue (label afterfib-n-2))      ; [n:0] [val:1] [continue:afterfib-n-2] [stack:(afterfib-n-2 2 fib-done)]
(save val)                                  ; [n:0] [val:1] [continue:afterfib-n-2] [stack:(1 afterfib-n-2 2 fib-done)]
(goto (label fib-loop))                     ; goto fib-loop
(test (op <) (reg n) (const 2))             ; (< 0 2) => true => goto immediate-answer
(assign val (reg n))                        ; [n:0] [val:0] [continue:afterfib-n-2] [stack:(1 afterfib-n-2 2 fib-done)]
(goto (reg continue))                       ; goto afterfib-n-2
(restore n)                                 ; [n:1] [val:0] [continue:afterfib-n-2] [stack:(afterfib-n-2 2 fib-done)]
(restore continue)                          ; [n:1] [val:0] [continue:afterfib-n-2] [stack:(2 fib-done)]
(assign val (op +) (reg val) (reg n))       ; [n:1] [val:1] [continue:afterfib-n-2] [stack:(2 fib-done)]
(goto (reg continue))                       ; goto afterfib-n-2
(restore n)                                 ; [n:2] [val:1] [continue:afterfib-n-2] [stack:(fib-done)]
(restore continue)                          ; [n:2] [val:1] [continue:fib-done] [stack:()]
(assign val (op +) (reg val) (reg n))       ; [n:2] [val:3] [continue:fib-done] [stack:()]
(goto (reg continue))                       ; goto fib-done

;; answer is 3 (val is 3)

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る