SICP 読書ノート#71 - 5.1 レジスタ計算機の設計 (pp.293-306)

色々と忙しくてサボってましたが、約半年ぶりに再開します。

Schemeを忘れていないかと心配でしたが、 4章までの苦労が染み付いてたせいか案外そうでもなかった。よかった！

5章を学ぶ意味

5章の冒頭にまとめてあります。

• 4章ではLispの言語解釈について学ぶことができたが、 Lisp制御システムのメカニズムまでは答えられていない
  • 例えば、部分式の評価や反復/再帰プロセスの生成の実現方法など
  • これは4章のLisp処理系がLispシステムの上に成り立っているから
• 5章ではこの残された謎を解くためレジスタマシンを実装しながら以下を学んでいく
  • §5.1では、レジスタマシンの命令列や設計について
  • §5.2では、レジスタマシンを動作させるシミュレータについて
  • §5.3では、consのメモリ演算やその割り当てについて
  • §5.4では、プリミティブな手続き(おそらくspecial form)を レジスタマシンに定式化する手法について
  • §5.5では、Schemeプログラムをレジスタマシンで 実行可能な命令列に翻訳するコンパイラについて

問題 5.1

テキストのgcdの例を参考に見よう見まねでやってみる。

factorialのデータパス図。

factorialの制御図。

問題 5.2

問題5.1のfactorialをレジスタマシン言語を使って書き直す。 アセンブリを書いているような気分。

ラベルの管理はどうしてるんだろうとか、testの結果は 特殊なレジスタに格納されるんだろなと色々と想像させられる。

(controller
 (assign product (const 1))
 (assign counter (const 1))
 test-counter
   (test (op >) (reg counter) (reg n))
   (branch (label factorial-done))
   (assign product (op *) (reg product) (reg counter))
   (assign counter (op +) (reg counter) (const 1))
   (goto (label test-counter))
 factorial-done)

問題 5.3

§1.1.7のニュートン法によって平方根を求めるマシンを設計する。

まずはデータパス図。

制御図は面倒なので省略。

マシン言語での実装。

(controller
 (assign x (op read))
 (assign guess (const 1.0))
 test-good-enough?
   (test (op good-enough?) (reg guess) (reg x))
   (branch (label sqrt-done))
   (assign guess (op remove) (reg guess) (reg x))
   (goto (label test-good-enough?))
 sqrt-done)

サブルーチンについて

サブルーチンと言えばスタックが必要になると思うが、 factorialのマシン言語の実装においても実際にそうなのか、 コントローラの命令シーケンス(instruction sequence)を追ってみた。

(controller
   (assign continue (label fact-done))     ; set up final return address
 fact-loop
   (test (op =) (reg n) (const 1))
   (branch (label base-case))
   ;; Set up for the recursive call by saving n and continue.
   ;; Set up continue so that the computation will continue
   ;; at after-fact when the subroutine returns.
   (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))   ; val now contains n * (n-1)!
   (goto (reg continue))                   ; return to caller
 base-case
   (assign val (const 1))                  ; base case: 1!=1
   (goto (reg continue))                   ; return to caller
 fact-done)

結果は以下の通り。サブルーチンの処理を実行する直前に それまでの途中の処理(=レジスタの値)をstackにsaveする。 そして、サブルーチンの処理が完了すると、 saveされた処理がrestoreされて途中だった処理を継続する。

step	instruction	val	n	continue	stack
1	(assign continue (label fact-done)		3	(label fact-done)
	fact-loop 1回目
2	(test (op =) (reg n) (const 1))		↓	↓
3	(save continue)		↓	↓	(label fact-done)
4	(save n)		↓	↓	3 (label fact-done)
5	(assign n (op -) (reg n) (const 1))		2	↓	↓
6	(assign continue (label after-fact))		↓	(label after-fact)	↓
7	(goto (label fact-loop))		↓	↓	↓
	fact-loop 2回目
8	(test (op =) (reg n) (const 1))		↓	↓	↓
9	(save continue)		↓	↓	(label after-fact) 3 (label fact-done)
10	(save n)		↓	↓	2 (label after-fact) 3 (label fact-done)
11	(assign n (op -) (reg n) (const 1))		1	↓	↓
12	(assign continue (label after-fact))		↓	(label after-fact)	↓
13	(goto (label fact-loop))		↓	↓	↓
	fact-loop 3回目
14	(test (op =) (reg n) (const 1)) => testの結果は真となる		↓	↓	↓
15	(branch (label base-case))		↓	↓	↓
	base-case 1回目
16	(assign val (const 1))	1	↓	↓	↓
17	(goto (reg continue))	↓	↓	↓	↓
	after-fact 1回目
18	(restore n)	↓	2	↓	(label after-fact) 3 (label fact-done)
19	(restore continue)	↓	↓	(label after-fact)	3 (label fact-done)
20	(assign val (op *) (reg n) (reg val))	2	↓	↓	↓
21	(goto (reg continue))	↓	↓	↓	↓
	after-fact 2回目
22	(restore n)	↓	3	↓	(label fact-done)
23	(restore continue)	↓	↓	(label fact-done)
24	(assign val (op *) (reg n) (reg val))	6	↓	↓
25	(goto (reg continue))	↓	↓	↓
	fact-done

問題 5.4

再帰的プロセスだとスタックが必ず必要、 反復的プロセスだと末尾再帰ならスタック不要、ということが言いたいんだと思う。

(a) 再帰的プロセス

(controller
 (assign continue (label expt-done))
 expt-loop
   (test (op =) (reg n) (const 0))
   (branch (label base-case))
   (save continue)
   (save n)
   (assign n (op -) (reg n) (const 1))
   (goto (label expt-loop))
 after-expt
   (restore n)
   (restore continue)
   (assign product (op *) (reg b) (reg product))
   (goto (reg controller))
 base-case
   (assign product (const 1))
   (goto (reg continue))
 expt-done)

データパス図。スタックから値を取り出す度にproductにbの値を掛け合わせて行く。

命令列のシーケンスは面倒なのでパス。

(b) 反復的プロセス

(controller
 (assign continue (reg n))
 (assign product (const 1))
 expt-loop
   (test (op =) (reg counter) (const 0))
   (branch (label expt-done))
   (assign counter (op -) (reg counter) (const 1))
   (assign product (op *) (reg b) (reg product))
   (goto (label expt-loop))
 expt-done)

データパス図。スタックがない分スッキリ。 初期値nのcounterを減らす度にproductにbを掛け合わせて行く。

アプリケーションからマシン語まで抽象レイヤーを降りてきても、 §1の初めの方でやったことがちゃんとつながるのが、SICPの凄いところだなあ。

問題 5.6

(save continue)と(restore continue)はなくても動く。

問題5.5と5.7はスキップで。

次は「§5.2 レジスタ計算機シミュレータ」から。

---

※「SICP読書ノート」の目次はこちら