Serendip

Web Studio

問題5.14

シミュレーターに 5.2.4 の修正を加えて、図5.11の階乗計算機を実行する。

(define fact-machine
  (make-machine
    '(continue val n)
    (list (list '= =) (list '- -) (list '* *))
    '(start
       (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 "fact:~2d => ~8d" n (get-register-contents fact-machine 'val))
  ((fact-machine 'stack) 'print-statistics)
  (newline))

(define (fact-iter n)
  (if (< n 10)
      (begin
        (fact n)
        (fact-iter (+ n 1)))))

実行結果

(fact-iter 1)
gosh> fact: 1 =>        1
(total-pushes = 0 maximum-depth = 0)
fact: 2 =>        2
(total-pushes = 2 maximum-depth = 2)
fact: 3 =>        6
(total-pushes = 4 maximum-depth = 4)
fact: 4 =>       24
(total-pushes = 6 maximum-depth = 6)
fact: 5 =>      120
(total-pushes = 8 maximum-depth = 8)
fact: 6 =>      720
(total-pushes = 10 maximum-depth = 10)
fact: 7 =>     5040
(total-pushes = 12 maximum-depth = 12)
fact: 8 =>    40320
(total-pushes = 14 maximum-depth = 14)
fact: 9 =>   362880
(total-pushes = 16 maximum-depth = 16)
#<undef>

fact = 2 * (n - 1) の式が成り立つ。

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

posted with amazlet at 08.11.07

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

Amazon.co.jp で詳細を見る