プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート

SICP 5.1.3 Subroutines

LISP Scheme

ノート

昔懐かしいBASICの世界。共通部分を括り出す。
括り出すステップ：

  1. それぞれのGCD計算部分の先頭にgcd-1、gcd-2のラベル、GCD計算部分を抜けた所にafter-gcd-1、after-gcd-2のラベルをつけている状態
  2. レジスタはGCDの計算区間でしか使用しないので共通のa、b、tを使用する
  3. レジスタcontinueにIDとなる数字を入れて、共通のラベルgcdに飛び、GCDの計算が終わった所でcontinueの値を見てafter-gcd-1かafter-gcd-2に飛ぶ
  4. レジスタにラベルを代入出来る事にして、レジスタcontinueにafter-gcd-1あるいはafter-gcd-2を代入する事でGCD計算が終わった部分を一般化

これで取り敢えずGCDの部分のコードに呼び出しもと依存の部分が無くなるが、レジスタcontinueが一つしか無いとGCDからサブルーチン（例えばrem）を呼び出す事が出来ない。と言う事で次節に繋がる。

5.1.4 Using a Stack to Implement Recursion

GCDは末尾再帰になっているがfactorialは(n-1)!を計算した後に掛け算が必要。末尾再帰であればレジスタをそのまま再利用出来るので単純なループで表現出来たが、factorialの場合は(n-1)!を計算している間もnは保持しておかなければならない。と言う事はfactorialの
factorialの計算をマシンで実現しようとするとfactorialマシンが無限に必要になってしまう。

物理的なマシンを再帰の度に再利用するにはレジスタの値を一旦退避して、あとから必要になった時に復元出来る仕組み＝スタックが必要。ここでは階乗を計算する値nとプログラム上の戻るべき場所（ラベル）continueをスタックにセーブする。

A double recursion

例示されているfibonacciマシンを図にしてみると

こんな感じか。

Exercise 5.4

a. 再帰の復路で計算するパターン
exptの戻り値を入れるレジスタをresultとすると、

  1. 再帰の度にnを一つずつ減らす
  2. nが0になったらresultを1で初期化して、再帰から戻り始める
  3. 再帰を戻る度にresultにbを掛けて代入する

nは実はresultの計算とは殆ど関係無くて、再帰する回数を決めているだけ。スタックには計算終了のラベルの次に、掛け算をする場所のラベルをn個積む事になる。

'(controller
  (assign continue (label expt-done))
  (save continue)
  expt-prep
  (test (op =) (reg n) (const 0))
  (branch (label expt-init))
  (assign n (op -) (reg n) (const 1))
  (assign continue (label expt-calc))
  (save continue)
  (goto (label expt-prep))
  expt-init
  (assign result (const 1))
  (restore continue)
  (goto (reg continue))
  expt-calc
  (assign result (op *) (reg result) (reg b))
  (restore continue)
  (goto (reg continue))
  expt-done)

b. 再帰の往路で計算するパターン
今度のレジスタはcountとproduct

  1. それぞれの初期値としてnと1を代入
  2. countが0であれば計算終了
  3. countからは1を引き、productにはbを掛ける

これを繰り返すだけなのでスタックは不要（何気なく末尾再帰の最適化になっている）。

'(controller
  (assign count (reg n))
  (assign product (const 1))
  expt-iter
  (test (op =) (reg count) (const 0))
  (branch (label expt-done))
  (assign count (op -) (reg count) (const 1))
  (assign product (op *) (reg product) (reg b))
  (goto (label expt-iter))
  expt-done)
Exercise 5.5

factorialの場合。3!を計算するとすると
（「significant pointで」と書いてあるけど、どの道全部書き出さないと分からない。）

ステップ 命令 val n continue stack
1 (assign continue (label fact-done)) 3 (label fact-done)
2 (test (op =) (reg n) (const 1)) 3 (label fact-done)
3 (save continue) 3 (label fact-done) (label fact-done)
4 (save n) 3 (label fact-done) 3/(label fact-done)
5 (assign n (op -) (reg n) (const 1)) 2 (label fact-done) 3/(label fact-done)
6 (assign continue (label after-fact)) 2 (label after-fact) 3/(label fact-done)
7 (goto (label fact-loop)) 2 (label after-fact) 3/(label fact-done)
8 (test (op =) (reg n) (const 1)) 2 (label after-fact) 3/(label fact-done)
9 (save continue) 2 (label after-fact) (label after-fact)/3/(label fact-done)
10 (save n) 2 (label after-fact) 2/(label after-fact)/3/(label fact-done)
11 (assign n (op -) (reg n) (const 1)) 1 (label after-fact) 2/(label after-fact)/3/(label fact-done)
12 (assign continue (label after-fact)) 1 (label after-fact) 2/(label after-fact)/3/(label fact-done)
13 (goto (label fact-loop) 1 (label after-fact) 2/(label after-fact)/3/(label fact-done)
14 (test (op =) (reg n) (const 1)) 1 (label after-fact) 2/(label after-fact)/3/(label fact-done)
15 (branch (label base-case)) 1 (label after-fact) 2/(label after-fact)/3/(label fact-done)
16 (assign val (const 1)) 1 1 (label after-fact) 2/(label after-fact)/3/(label fact-done)
17 (goto (reg continue)) 1 1 (label after-fact) 2/(label after-fact)/3/(label fact-done)
18 (restore n) 1 2 (label after-fact) (label after-fact)/3/(label fact-done)
19 (restore continue) 1 2 (label after-fact) 3/(label fact-done)
20 (assign val (op *) (reg n) (reg val)) 2 2 (label after-fact) 3/(label fact-done)
21 (goto (reg continue)) 2 2 (label after-fact) 3/(label fact-done)
22 (restore n) 2 3 (label after-fact) (label fact-done)
23 (restore continue) 2 3 (label fact-done)
24 (assign val (op *) (reg n) (reg val)) 6 3 (label fact-done)
25 (goto (reg continue)) 6 3 (label fact-done)

Fibonacciの場合。Fib(5)を計算するとすると。

ステップ 命令 val n continue stack
1 (assign continue (label fib-done)) 5 (label fib-done)
2 (test (op <) (reg n) (const 2)) 5 (label fib-done)
3 (save continue) 5 (label fib-done) (label fib-done)
4 (assign continue (label afterfib-n-1)) 5 (label afterfib-n-1) (label fib-done)
5 (save n) 5 (label afterfib-n-1) 5/(label fib-done)
6 (assign n (op -) (reg n) (const 1)) 4 (label afterfib-n-1) 5/(label fib-done)
7 (goto (label fib-loop)) 4 (label afterfib-n-1) 5/(label fib-done)
8 (test (op <) (reg n) (const 2) 4 (label afterfib-n-1) 5/(label fib-done)
9 (save continue) 4 (label afterfib-n-1) (label afterfib-n-1)/5/(label fib-done)
10 (assign continue (label afterfib-n-1)) 4 (label afterfib-n-1) (label afterfib-n-1)/5/(label fib-done)
11 (save n) 4 (label afterfib-n-1) 4/(label afterfib-n-1)/5/(label fib-done)
12 (assign n (op -) (reg n) (const 1)) 3 (label afterfib-n-1) 4/(label afterfib-n-1)/5/(label fib-done)
13 (goto (label fib-loop)) 3 (label afterfib-n-1) 4/(label afterfib-n-1)/5/(label fib-done)
14 (test (op <) (reg n) (const 2) 3 (label afterfib-n-1) 4/(label afterfib-n-1)/5/(label fib-done)
15 (save continue) 3 (label afterfib-n-1) (label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
16 (assign continue (label afterfib-n-1)) 3 (label afterfib-n-1) (label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
17 (save n) 3 (label afterfib-n-1) 3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
18 (assign n (op -) (reg n) (const 1)) 2 (label afterfib-n-1) 3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
19 (goto (label fib-loop)) 2 (label afterfib-n-1) 3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
20 (test (op <) (reg n) (const 2) 2 (label afterfib-n-1) 3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
21 (save continue) 2 (label afterfib-n-1) (label afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
22 (assign continue (label afterfib-n-1)) 2 (label afterfib-n-1) (label afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
23 (save n) 2 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
24 (assign n (op -) (reg n) (const 1)) 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
25 (goto (label fib-loop)) 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
26 (test (op <) (reg n) (const 2) 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
27 (branch (label immediate-answer)) 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
28 (assign val (reg n)) 1 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
29 (goto (reg continue)) 1 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
30 (restore n) 1 2 (label afterfib-n-1) (label afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
31 (restore continue) 1 2 (label afterfib-n-1) 3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
32 (assign n (op -) (reg n) (const 2)) 1 0 (label afterfib-n-1) 3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
33 (save continue) 1 0 (label afterfib-n-1) (afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
34 (assign continue (label afterfib-n-2)) 1 0 (label afterfib-n-2) (afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
35 (save val) 1 0 (label afterfib-n-2) 1/(afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
36 (goto (label fib-loop)) 1 0 (label afterfib-n-2) 1/(afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
37 (test (op <) (reg n) (const 2)) 1 0 (label afterfib-n-2) 1/(afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
38 (branch (label immediate-answer)) 1 0 (label afterfib-n-2) 1/(afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
39 (assign val (reg n)) 0 0 (label afterfib-n-2) 1/(afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
40 (goto (reg continue)) 0 0 (label afterfib-n-2) 1/(afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
41 (assign n (reg val)) 0 0 (label afterfib-n-2) 1/(afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
42 (restore val) 1 0 (label afterfib-n-2) (afterfib-n-1)/3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
43 (restore continue) 1 0 (label afterfib-n-1) 3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
44 (assign val (op +) (reg val) (reg n)) 1 0 (label afterfib-n-1) 3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
45 (goto (reg continue)) 1 0 (label afterfib-n-1) 3/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
46 (restore n) 1 3 (label afterfib-n-1) (label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
47 (restore continue) 1 3 (label afterfib-n-1) (label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
48 (assign n (op -) (reg n) (const 2)) 1 1 (label afterfib-n-1) (label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
49 (save continue) 1 1 (label afterfib-n-1) (label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
50 (assign continue (label afterfib-n-2)) 1 1 (label afterfib-n-2) (label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
51 (save val) 1 1 (label afterfib-n-2) 1/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
52 (goto (label fib-loop)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
53 (test (op <) (reg n) (const 2)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
54 (branch (label immediate-answer)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
55 (assign val (reg n)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
56 (goto (reg continue)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
57 (assign n (reg val)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
58 (restore val) 1 1 (label afterfib-n-2) (label afterfib-n-1)/4/(label afterfib-n-1)/5/(label fib-done)
59 (restore continue) 1 1 (label afterfib-n-1) 4/(label afterfib-n-1)/5/(label fib-done)
60 (assign val (op +) (reg val) (reg n)) 2 1 (label afterfib-n-1) 4/(label afterfib-n-1)/5/(label fib-done)
61 (goto (reg continue)) 2 1 (label afterfib-n-1) 4/(label afterfib-n-1)/5/(label fib-done)
62 (restore n) 2 4 (label afterfib-n-1) (label afterfib-n-1)/5/(label fib-done)
63 (restore continue) 2 4 (label afterrfib-n-1) 5/(label fib-done)
64 (assign n (op -) (reg n) (const 2)) 2 2 (label afterrfib-n-1) 5/(label fib-done)
65 (save continue) 2 2 (label afterfib-n-1) (label afterfib-n-1)/5/(label fib-done)
66 (assign continue (label afterfib-n-2)) 2 2 (label afterfib-n-2) (label afterfib-n-1)/5/(label fib-done)
67 (save val) 2 2 (label afterfib-n-2) 2/(label afterfib-n-1)/5/(label fib-done)
68 (goto (label fib-loop)) 2 2 (label afterfib-n-2) 2/(label afterfib-n-1)/5/(label fib-done)
69 (test (op <) (reg n) (const 2)) 2 2 (label afterfib-n-2) 2/(label afterfib-n-1)/5/(label fib-done)
70 (save continue) 2 2 (label afterfib-n-2) (label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
71 (assign continue (label afterfib-n-1)) 2 2 (label afterfib-n-1) (label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
72 (save n) 2 2 (label afterfib-n-1) 2/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
73 (assign n (op -) (reg n) (const 1)) 2 1 (label afterfib-n-1) 2/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
74 (goto (label fib-loop)) 2 1 (label afterfib-n-1) 2/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
75 (test (op <) (reg n) (const 2)) 2 1 (label afterfib-n-1) 2/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
75 (branch (label immediate-answer)) 2 1 (label afterfib-n-1) 2/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
76 (assign val (reg n)) 1 1 (label afterfib-n-1) 2/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
77 (goto (reg continue)) 1 1 (label afterfib-n-1) 2/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
78 (restore n) 1 2 (label afterfib-n-1) (label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
79 (restore continue) 1 2 (label afterfib-n-2) 2/(label afterfib-n-1)/5/(label fib-done)
80 (assign n (op -) (reg n) (const 2)) 1 0 (label afterfib-n-2) 2/(label afterfib-n-1)/5/(label fib-done)
81 (save continue) 1 0 (label afterfib-n-2) (label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
82 (assign continue (label afterfib-n-2)) 1 0 (label afterfib-n-2) (label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
83 (save val) 1 0 (label afterfib-n-2) 1/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
84 (goto (label fib-loop)) 1 0 (label afterfib-n-2) 1/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
85 (test (op <) (reg n) (const 2)) 1 0 (label afterfib-n-2) 1/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
86 (branch (label immediate-answer)) 1 0 (label afterfib-n-2) 1/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
87 (assign val (reg n)) 0 0 (label afterfib-n-2) 1/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
88 (goto (reg continue)) 0 0 (label afterfib-n-2) 1/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
89 (assign n (reg val)) 0 0 (label afterfib-n-2) 1/(label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
90 (restore val) 1 0 (label afterfib-n-2) (label afterfib-n-2)/2/(label afterfib-n-1)/5/(label fib-done)
91 (restore continue) 1 0 (label afterfib-n-2) 2/(label afterfib-n-1)/5/(label fib-done)
92 (assign val (op +) (reg val) (reg n)) 1 0 (label afterfib-n-2) 2/(label afterfib-n-1)/5/(label fib-done)
93 (goto (reg continue)) 1 0 (label afterfib-n-2) 2/(label afterfib-n-1)/5/(label fib-done)
94 (assign n (reg val)) 1 1 (label afterfib-n-2) 2/(label afterfib-n-1)/5/(label fib-done)
95 (restore val) 2 1 (label afterfib-n-2) (label afterfib-n-1)/5/(label fib-done)
96 (restore continue) 2 1 (label afterfib-n-1) 5/(label fib-done)
97 (assign val (op +) (reg val) (reg n)) 3 1 (label afterfib-n-1) 5/(label fib-done)
98 (goto (reg continue)) 3 1 (label afterfib-n-1) 5/(label fib-done)
99 (restore n) 3 5 (label afterfib-n-1) (label fib-done)
100 (restore continue) 3 5 (label fib-done)
101 (assign n (op -) (reg n) (const 2)) 3 3 (label fib-done)
102 (save continue) 3 3 (label fib-done) (label fib-done)
103 (assign continue (label afterfib-n-2)) 3 3 (label afterfib-n-2) (label fib-done)
104 (save val) 3 3 (label afterfib-n-2) 3/(label fib-done)
105 (goto (label fib-loop)) 3 3 (label afterfib-n-2) 3/(label fib-done)
106 (test (op <) (reg n) (const 2)) 3 3 (label afterfib-n-2) 3/(label fib-done)
107 (save continue) 3 3 (label afterfib-n-2) (label afterfib-n-2)/3/(label fib-done)
108 (assign continue (label afterfib-n-1)) 3 3 (label afterfib-n-1) (label afterfib-n-2)/3/(label fib-done)
109 (save n) 3 3 (label afterfib-n-1) 3/(label afterfib-n-2)/3/(label fib-done)
110 (assign n (op -) (reg n) (const 1)) 3 2 (label afterfib-n-1) 3/(label afterfib-n-2)/3/(label fib-done)
111 (goto (label fib-loop)) 3 2 (label afterfib-n-1) 3/(label afterfib-n-2)/3/(label fib-done)
112 (test (op <) (reg n) (const 2)) 3 2 (label afterfib-n-1) 3/(label afterfib-n-2)/3/(label fib-done)
113 (save continue) 3 2 (label afterfib-n-1) (label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
114 (assign continue (label afterfib-n-1)) 3 2 (label afterfib-n-1) (label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
115 (save n) 3 2 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
116 (assign n (op -) (reg n) (const 1)) 3 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
117 (goto (label fib-loop)) 3 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
118 (test (op <) (reg n) (const 2)) 3 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
119 (branch (label immediate-answer)) 3 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
120 (assign val (reg n)) 1 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
121 (goto (reg continue)) 1 1 (label afterfib-n-1) 2/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
122 (restore n) 1 2 (label afterfib-n-1) (label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
123 (restore continue) 1 2 (label afterfib-n-1) 3/(label afterfib-n-2)/3/(label fib-done)
124 (assign n (op -) (reg n) (const 2)) 1 0 (label afterfib-n-1) 3/(label afterfib-n-2)/3/(label fib-done)
125 (save continue) 1 0 (label afterfib-n-1) (label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
126 (assign continue (label afterfib-n-2)) 1 0 (label afterfib-n-2) (label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
127 (save val) 1 0 (label afterfib-n-2) 1/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
128 (goto (label fib-loop)) 1 0 (label afterfib-n-2) 1/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
129 (test (op <) (reg n) (const 2)) 1 0 (label afterfib-n-2) 1/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
130 (branch (label immediate-answer)) 1 0 (label afterfib-n-2) 1/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
131 (assign val (reg n)) 0 0 (label afterfib-n-2) 1/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
132 (goto (reg continue)) 0 0 (label afterfib-n-2) 1/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
133 (assign n (reg val)) 0 0 (label afterfib-n-2) 1/(label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
134 (restore val) 1 0 (label afterfib-n-2) (label afterfib-n-1)/3/(label afterfib-n-2)/3/(label fib-done)
135 (restore continue) 1 0 (label afterfib-n-1) 3/(label afterfib-n-2)/3/(label fib-done)
136 (assign val (op +) (reg val) (reg n)) 1 0 (label afterfib-n-1) 3/(label afterfib-n-2)/3/(label fib-done)
137 (goto (reg continue)) 1 0 (label afterfib-n-1) 3/(label afterfib-n-2)/3/(label fib-done)
138 (restore n) 1 3 (label afterfib-n-1) (label afterfib-n-2)/3/(label fib-done)
139 (restore continue) 1 3 (label afterfib-n-2) 3/(label fib-done)
140 (assign n (op -) (reg n) (const 2)) 1 1 (label afterfib-n-2) 3/(label fib-done)
141 (save continue) 1 1 (label afterfib-n-2) (label afterfib-n-2)/3/(label fib-done)
142 (assign continue (label afterfib-n-2)) 1 1 (label afterfib-n-2) (label afterfib-n-2)/3/(label fib-done)
143 (save val) 1 1 (label afterfib-n-2) 1/(label afterfib-n-2)/3/(label fib-done)
144 (goto (label fib-loop)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-2)/3/(label fib-done)
145 (test (op <) (reg n) (const 2)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-2)/3/(label fib-done)
146 (branch (label immediate-answer)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-2)/3/(label fib-done)
147 (assign val (reg n)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-2)/3/(label fib-done)
148 (goto (reg continue)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-2)/3/(label fib-done)
149 (assign n (reg val)) 1 1 (label afterfib-n-2) 1/(label afterfib-n-2)/3/(label fib-done)
150 (restore val) 1 1 (label afterfib-n-2) (label afterfib-n-2)/3/(label fib-done)
151 (restore continue) 1 1 (label afterfib-n-2) 3/(label fib-done)
152 (assign val (op +) (reg val) (reg n)) 2 1 (label afterfib-n-2) 3/(label fib-done)
153 (goto (reg continue)) 2 1 (label afterfib-n-2) 3/(label fib-done)
154 (assign n (reg val)) 2 2 (label afterfib-n-2) 3/(label fib-done)
155 (restore val) 3 2 (label afterfib-n-2) (label fib-done)
156 (restore continue) 3 2 (label fib-done)
157 (assign val (op +) (reg val) (reg n)) 5 2 (label fib-done)
158 (goto (reg continue)) 5 2 (label fib-done)
Exercise 5.6

Exercise 5.5を手で書いていると直ぐに気付く。以下の部分

 afterfib-n-1
   (restore n)
   (restore continue)  ;; ←これと
   ;; set up to compute Fib(n - 2)
   (assign n (op -) (reg n) (const 2))
   (save continue)  ;; ←これ

continueにrestoreしたラベルをまたそのままスタックに積むので無駄。

5.1.5 Instruction Summary

ここは纏めだけなので特にノートは無し。