SICP演習問題5.1~5.6

やっと5章です．もう少しで終わりなのです．ついに！

5.1，5.4,5.5はノートに書いた．

5.2

;; exercise 5.2
(controller
 init
    (assign p (const 1))
    (assign c (const 1))
 test-c
    (test (op >) (reg c) (const n))
    (branch (label init-done))
    (assign t (op mul) (reg p) (reg c))
    (assign s (op add) (reg c) (const 1))
    (assign p (reg t))
    (assign c (reg s))
    (goto (label test-c))
 init-done)

5.3

;; exercise 5.3
(controller
 sqrt
    (assign guess 1.0)
 sqrt-iter
 ; good-enough?
    (assign sq (op *) (reg guess) (reg guess))
    (assign a (op -) (reg sq) (reg x))
    (assign b (op abs) (reb a))
    (test (op <) (reg b) (const 0.001))
    (branch (label sqrt-done))
 ; improve
    (assign c (op /) (reg x) (reg guess))
    (assign d (op +) (reg guess) (reg c))
    (assign guess (op /) (reg d) (const 2))
    (goto sqrt-iter)
 sqrt-done)

5.4

;; a
(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

(controller
    (assign continue (label expt-done))
 expt-loop
    (test (op =) (reg n) (const 0))
    (branch (label base-case))
    (save continue)
    (assign n (op -) (reg n) (const 1))
    (assign continue (label after-expt))
    (goto (label expt-loop))
 after-expt
    (restore continue)
    (assign val (op *) (reg b) (reg val))
    (goto (reg continue))
 base-case
    (assign val (const 1))
    (goto (reg continue))
 fact-done)

;; b
(define (expt b n)
  (define (expt-iter counter product)
    (if (= counter 0)
        product
        (expt-iter (- counter 1) (* b counter))))
  (expt-iter n 1))

(controller
 expt
    (assign counter (reg n))
    (assign product (const 1))
 expt-iter
    (test (op =) (reg counter) (const 0))
    (branch (label expt-done))
    (assign product (op *) (reg b) (reg product))
    (assign counter (op -) (reg counter) (const 1))
    (goto (label expt-iter))
 expt-done)

5.6

以下の「不要」と書いたところが余分．
机上シュミレートwをしてみるとわかる．

(controller
    (assign continue (label fib-done))
 fib-loop
    (test (op <) (reg n) (const 2))
    (branch (label immediate-answer))
    ;; set up to compute Fib(n-1)
    (save continue)
    (assign continue (label afterfib-n-1))
    (save n)
    (assign n (op -) (reg n) (const 1))
    (goto (label fib-loop))
 afterfib-n-1
    (restore n)
    (restore continue)  ; 不要
    ;; set up to compute Fib(n-2)
    (assign n (op -) (reg n) (const 2))
    (save continue)　　　; 不要
    (assign continue (label afterfib-n-2))
    (save val)
    (goto (label fib-loop))
 afterfib-n-2
    (assign n (reg val))
    (restore val)
    (restore continue)
    (assign val
            (op +) (reg val) (reg n))
    (goto (reg continue))
 immediate-answer
    (assign val (reg n))
    (goto (reg continue))
 fib-done)