Serendip

Web Studio

問題5.5

再帰的階乗計算機

(controller
    (assign continue (label fact-done))
  fact-loop
    (test (op =) (reg n) (const 1))
    (branch (label base-case))
    ;; n と continue を退避し再帰呼び出しを設定する
    ;; 再帰呼び出しから戻る時 after-fact から
    ;; 計算が続行するように continue を設定
    (save continue)
    (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)) ; val に n(n-1)! がある
    (goto (reg continue))                 ; 呼び出し側に戻る
  base-case
    (assign val (const 1))                ; 基底の場合 1! = 1
    (goto (reg continue))                 ; 呼び出し側に戻る
  fact-done)

上記の再帰的階乗計算機を使って 3! を計算してみる。
n の初期値は 3 となる、(assign n (op read)) でセットされたものとする。
スタックの内容をリストで表現する。

(assign continue (label fact-done))     ; continue を fact-done にセット

(test (op =) (reg n) (const 1))         ; n は 3 のため false

(save continue)                         ; continue のスタックは (fact-done)

(save n)                                ; n のスタックは (3)

(assign n (op -) (reg 3) (const 1))     ; n に 2 をセット

(assign continue (label after-fact))    ; continue に after-fact をセット

(goto (label fact-loop))                ; ラベル fact-loop に移動

(test (op =) (reg n) (const 1))         ; n は 2 のため false

(save continue)                         ; continue のスタックは (after-fact fact-done)

(save n)                                ; n のスタックは (2 3)

(assign n (op -) (reg 2) (const 1))     ; n に 1 をセット

(assign continue (label after-fact))    ; continue に after-fact をセット

(goto (label fact-loop))                ; ラベル fact-loop に移動

(test (op =) (reg n) (const 1))         ; n は 1 のため true

(branch (label base-case))              ; ラベル base-case に移動

(assign val (const 1))                  ; val に 1 をセット

(goto (reg continue))                   ; continue の値 after-fact に移動

(restore n)                             ; スタックから restore して n に 2 をセット、 n のスタックは (3)

(restore continue)                      ; スタックから restore して continue に after-fact をセット、 continue のスタックは (fact-done)

(assign val (op *) (reg n) (reg val))   ; n は 2、 val は 1 により val に 2 をセット

(goto (reg continue))                   ; continue の値 after-fact に移動

(restore n)                             ; スタックから restore して n に 3 をセット、n スタックは空

(restore continue)                      ; スタックから restore して continue に fact-done をセット、 continue のスタックは空

(assign val (op *) (reg n) (reg val))   ; n は 3、val は 2 により val に 6 をセット

(goto (reg continue))                   ; continue の値 fact-done に移動

fact-done                               ; 最終的な結果 val の値は 6

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

posted with amazlet at 08.11.07

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

Amazon.co.jp で詳細を見る