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)回になる.