SICP 読み (242) 5.1 レジスタ計算機の設計
問題 5.5
正に Hand Simulate な手法で試みてみます。
しかも数値を順に上げてみる。最初は 1 で (0 は略)
(assign continue (label fib-done)) ;; 最初は fib-done を格納 (test (op <) (reg n) (const 2)) ;; n は 1 (branch (label immediate-answer)) ;; immediate-answer に jmp (assign val (reg n)) ;; val に n の値 (1) が格納 (goto (reg continue)) ;; fib-done に jmp
次、n が 2 の場合
(assign continue (label fib-done)) ;; 最初は fib-done を格納
(test (op <) (reg n) (const 2)) ;; n は 2 なので branch はスルー
(save continue) ;; push して afterfib-n-1 を設定
(assign continue (label afterfib-n-1))
(save n) ;; 2 な n を push
(assign n (op -) (reg n) (const 1));; n に (- n 1) をセット
(goto (label fib-loop)) ;; fib-loop に戻る
;; (1)
(test (op <) (reg n) (const 2)) ;; n の値は 1
(branch (label immediate-answer)) ;; immediate-answer に jmp
(assign val (reg n)) ;; val に 1 を格納
(goto (reg continue)) ;; continue は afterfib-n-1
(restore n) ;; n を pop すると 2
(restore continue) ;; continue は fib-done に
;; (2)
;; set up to compute Fib(n - 2)
(assign n (op -) (reg n) (const 2));; n に (- n 2) をセット
(save continue) ;; 再度 fib-done を push
;; continue は afterfib-n-2 に
(assign continue (label afterfib-n-2))
(save val) ;; 1 な val を push
(goto (label fib-loop)) ;; fib-loop に戻る
;; (3)
(test (op <) (reg n) (const 2)) ;; n は 0
(branch (label immediate-answer)) ;; immediate-answer に jmp
(assign val (reg n)) ;; val が 0 に
(goto (reg continue)) ;; afterfib-n-2 に jmp
(assign n (reg val)) ;; n に 0 が格納
(restore val) ;; val を pop (1 に)
(restore continue) ;; continue は fib-done
(assign val ;; (+ 1 0) を val にセット
(op +) (reg val) (reg n))
(goto (reg continue)) ;; fib-done に jmpstack の状態確認してみるか。ってか、このレジスタ計算機というヤツは stack は一つなんだよな。順番もおそらく意識されているはず。まず (1) の stack の状態。リストで表現しちゃれ。
(2 fib-done)
で、(2) の直前で restore してるから stack は空ッスか??
()
次に (3) の直前で val と fib-done を save しています。
(1 fib-done)
最後に val、continue の順で pop している。
これはサブルーチン呼び出し元のレジスタの値と戻り番地を stack に push しといてサブルーチンに制御を渡してる、と見て良いのかなぁ。で、上記の (fib 2) の場合は (fib 1) から戻って n と continue を復帰 (pop) しているのが分かる。
次に (fib 0) を呼び出すんだけど、そん時に退避してるのは continue と val だな。パターンとしては fib なツリーの left branch な呼び出しの時には n と continue を save して right branch な呼び出し時には val と continue を save しているのでしょうか。ソース見るにそんな感じですな。(fib 3) も見てみます。
(assign continue (label fib-done)) ;; 最初は fib-done を格納
(test (op <) (reg n) (const 2)) ;; n は 3 なので branch はスルー
(save continue) ;; push して afterfib-n-1 を設定
(assign continue (label afterfib-n-1))
(save n) ;; 3 な n を push
(assign n (op -) (reg n) (const 1));; n に (- n 1) をセット
(goto (label fib-loop)) ;; fib-loop に戻る
;; stack condition is
;; (3 fib-done)
(test (op <) (reg n) (const 2)) ;; n は 2 なので branch はスルー
(save continue) ;; push されるのは afterfib-n-1
;; continue には afterfib-n-1 がセット
(assign continue (label afterfib-n-1))
(save n) ;; 2 な n を push
(assign n (op -) (reg n) (const 1));; n に (- n 1) をセット
(goto (label fib-loop)) ;; fib-loop に戻る
;; stack condition is
;; (2 afterfib-n-1 3 fib-done)
(test (op <) (reg n) (const 2)) ;; n の値は 1
(branch (label immediate-answer)) ;; immediate-answer に jmp
(assign val (reg n)) ;; val に 1 を格納
(goto (reg continue)) ;; continue は afterfib-n-1
(restore n) ;; n を pop すると 2
(restore continue) ;; continue は afterfib-n-1
;; stack condition is
;; (3 fib-done)
(assign n (op -) (reg n) (const 2));; n に (- n 2) をセット
(save continue) ;; afterfib-n-1 を save
;; continue は afterfib-n-2
(assign continue (label afterfib-n-2))
(save val) ;; 1 な val を退避
(goto (label fib-loop))
;; stack condition is
;; (1 afterfib-n-1 3 fib-done)
(test (op <) (reg n) (const 2)) ;; n の値は 0
(branch (label immediate-answer)) ;; immediate-answer に jmp
(assign val (reg n)) ;; val に 0 をセット
(goto (reg continue)) ;; afterfib-n-2 に jmp
(assign n (reg val)) ;; val の値を n に退避
(restore val) ;; val を復帰 (1 に)
(restore continue) ;; continue 復帰 (afterfib-n-1 に)
(assign val ;; (+ val n) を val にセット
(op +) (reg val) (reg n))
(goto (reg continue)) ;; afterfib-n-1 に jmp
;; コメントに return to caller とある
;; stack condition is
;; (3 fib-done)
(restore n) ;; n を復帰 (3 に)
(restore continue) ;; continue を復帰 (fib-done に)
;; set up to compute Fib(n - 2)
(assign n (op -) (reg n) (const 2));; n に (- n 2) をセット
(save continue) ;; continue (fib-done) を退避して
;; continue を afterfib-n-2 に
(assign continue (label afterfib-n-2))
(save val) ;; val (1) を退避
(goto (label fib-loop))
;; stack condition is
;; (1 fib-done)
(test (op <) (reg n) (const 2)) ;; n の値は 1
(branch (label immediate-answer)) ;; immediate-answer に jmp
(assign val (reg n)) ;; val に 1 をセット
(goto (reg continue)) ;; afterfib-n-2 に jmp
(assign n (reg val)) ;; val の値を n に退避
(restore val) ;; val を復帰 (1 に)
(restore continue) ;; continue を復帰 (fib-done に)
(assign val ;; val に (+ val n) をセット
(op +) (reg val) (reg n)) ;; val の値は 2 になる
(goto (reg continue)) ;; fib-done に jmpよく木だけじゃなくって森を見れ、みたいなコトを言ってるんですが、直列な手続きでソレをやるのは結構キビしいなぁ。ってか慣れてないよ。ただ、left だの right だのという特性はビンゴに見える。
ただ、次の問題にある_余分な save と余分な restore_ってのはまだ見えてません。(immediate-answer??) とりあえず控えを投入しておく、という事で。
追記
テキストの 21p. にあるような fib のマンガを見つつポイントを列挙してみたので控えを以下に出力。
- left-branch の前な処理 (fib-loop なブロック)
- 全ての分岐で実行される
- 末端も同様だが条件分岐で immediate-answer に jmp
- push continue (基本的には afterfib-n-1)
- push n
- その後、n に (- n 1) をセットして fib-loop に jmp
- right-branch の前 (left-branch の後) な処理 (afterfib-n-1 なブロック)
- pop n
- pop continue
- push continue
- push val
- continue の取り扱いは微妙 (これも問題 5.6 な解の一つ??)
- n に (- n 2) を、continue に afterfib-n-2 をセットして fib-loop に jmp
- right-branch の後 (afterfib-n-2 なブロック)
- n <- val
- pop val
- pop continue
- val に (+ val n) をセットして continue に jmp
- 末端の処理 (n が 0 又は 1 の場合)
- val <- n (n は 0 又は 1)
- continue に jmp
上記を見ても早くなり得る余分なソレは afterfib-n-1 にある continue の復帰とその直後の退避だけに見えます。他にもあるのかなぁ。無いハズなんですが ...
追記
以下の一連の手続きについてメモ。
(define (assemble controller-text machine)
(extract-labels controller-text
(lambda (insts labels)
(update-insts! insts labels machine)
insts)))
(define (extract-labels text receive)
(if (null? text)
(receive '() '())
(extract-labels (cdr text)
(lambda (insts labels)
(let ((next-inst (car text)))
(if (symbol? next-inst)
(receive insts
(cons (make-label-entry next-inst
insts)
labels))
(receive (cons (make-instruction next-inst)
insts)
labels)))))))合ってるかどうかは微妙ですが。
extract-labels の中で再帰的に呼び出されてる extract-labels に渡されている手続きオブジェクトが持ってる receive は assemble の中で extract-labels に渡されている
(lambda (insts labels)
(update-insts! insts labels machine)
insts)てーコトになると見てるんですがダウト??
てか、脚注で_継続_な単語が出ているんですが何だこれは。
