読者です 読者をやめる 読者になる 読者になる

(wat-aro)

無職から有職者にランクアップしました

SICP 問題 5.14

(define fact-machine
  (make-machine
   '(continue n val)
   (list (list '= =) (list '- -) (list '* *) (list 'print print))
   '(controller
     (assign continue (label fact-done))
     fact-loop
     (test (op =) (reg n) (const 1))
     (branch (label base-case))
     (save continue)
     (save n)
     (assign n (op -) (reg n) (const 1))
     (assign continue (label after-fact))
     (goto (label fact-loop))
     after-fact
     (restore n)
     (restore continue)
     (assign val (op *) (reg n) (reg val))
     (goto (reg continue))
     base-case
     (assign val (const 1))
     (goto (reg continue))
     fact-done)))

(define (fact n)
  ((fact-machine 'stack) 'initialize)
  (set-register-contents! fact-machine 'n n)
  (start fact-machine)
  (format #t "factorial: ~2d = ~10d" n (get-register-contents fact-machine 'val))
  ((fact-machine 'stack) 'print-statistics)
  (newline))

(define (display-fact n)
  (let iter ((k 1))
    (if (= k n)
        (fact k)
        (begin (fact k)
               (iter (+ k 1))))))
gosh> (display-fact 10)
factorial:  1 =          1
(total-pushes = 0 maximum-depth = 0)
factorial:  2 =          2
(total-pushes = 2 maximum-depth = 2)
factorial:  3 =          6
(total-pushes = 4 maximum-depth = 4)
factorial:  4 =         24
(total-pushes = 6 maximum-depth = 6)
factorial:  5 =        120
(total-pushes = 8 maximum-depth = 8)
factorial:  6 =        720
(total-pushes = 10 maximum-depth = 10)
factorial:  7 =       5040
(total-pushes = 12 maximum-depth = 12)
factorial:  8 =      40320
(total-pushes = 14 maximum-depth = 14)
factorial:  9 =     362880
(total-pushes = 16 maximum-depth = 16)
factorial: 10 =    3628800
(total-pushes = 18 maximum-depth = 18)
#<undef>

total-depth, maximum-depthともに2(n-1)回になる.