Serendip

Web Studio

問題5.6

余分な save と restore は、afterfib-n-1 の (restore continue) と (save continue) の2ヶ所。
スタックから取り出したものをそのまま再びスタックに入れている。

(fib 4) として、n と val と continue のスタック処理内容を書き出してみる。

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

訂正：スタックはレジスタ毎に分かれておらず、1つのスタックで管理されている。

                                            ; [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
(assign n (reg val))                        ; [n:0] [val:0] [continue:afterfib-n-2] [stack:(1 afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(restore val)                               ; [n:0] [val:1] [continue:afterfib-n-2] [stack:(afterfib-n-1 3 afterfib-n-1 4 fib-done)]
(restore continue)                          ; [n:0] [val:1] [continue:afterfib-n-1] [stack:(3 afterfib-n-1 4 fib-done)]
(assign val (op +) (reg val) (reg n))       ; [n:0] [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 (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-2] [stack:(1 afterfib-n-1 4 fib-done)]
(goto (reg continue))                       ; goto afterfib-n-2
(assign n (reg val))                        ; [n:1] [val:1] [continue:afterfib-n-2] [stack:(1 afterfib-n-1 4 fib-done)]
(restore val)                               ; [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 (label 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
(assign n (reg val))                        ; [n:0] [val:0] [continue:afterfib-n-2] [stack:(1 afterfib-n-2 2 fib-done)]
(restore val)                               ; [n:0] [val:1] [continue:afterfib-n-2] [stack:(afterfib-n-2 2 fib-done)]
(restore continue)                          ; [n:0] [val:1] [continue:afterfib-n-2] [stack:(2 fib-done)]
(assign val (op +) (reg val) (reg n))       ; [n:0] [val:1] [continue:afterfib-n-2] [stack:(2 fib-done)]
(goto (reg continue))                       ; goto afterfib-n-2
(assign n (reg val))                        ; [n:1] [val:1] [continue:afterfib-n-2] [stack:(2 fib-done)]
(restore val)                               ; [n:1] [val:2] [continue:afterfib-n-2] [stack:(fib-done)]
(restore continue)                          ; [n:1] [val:2] [continue:fib-done] [stack:()]
(assign val (op +) (reg val) (reg n))       ; [n:1] [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 で詳細を見る