5.1 图就不画在机器上了，麻烦
5.2 用寄存器语言描述5.1题中的阶乘机器，加上了读取和打印,这里的解答全部在实际的寄存机器中验证过，但是仍然按照该节的表示法表示。
(controller fac
-
loop (assign n (op read)) (assign product (
const
1
)) (assign counter (
const
1
)) iter
-
loop (test (op
>
) (reg counter) (reg n)) (branch (label iter
-
done)) (assign product (op
*
) (reg product) (reg counter)) (assign counter (op
+
) (reg counter) (
const
1
)) (
goto
(label iter
-
loop)) iter
-
done (perform (op print) (reg product)) (
goto
(label fac
-
loop)))
5.3 牛顿法求平方根，将这个过程转化为寄存器语言，第一个版本，假设good-enough?和improve都是基本过程，
;version1 (controller sqrt
-
loop (test (op good
-
enough
?
) (reg guess)) (branch (label sqrt
-
done)) (assign guess (op improve) (reg guess)) (
goto
(label good
-
enough)) sqrt
-
done)
第二个版本，展开good-enough?过程，
;version2 (controller good
-
enough (assign t (op square) (reg guess)) (assign t (op
-
) (reg t) (reg x)) (assign t (op abs) (reg t)) (test (op
<
) (reg t) (
const
0.001
)) (branch (label sqrt
-
done)) (assign guess (op improve) (reg guess)) (
goto
(label good
-
enough)) sqrt
-
done)
最后，展开improve过程，
;version3 (controller sqrt-init (assign guess (const 1.0)) (assign x (op read)) good
-
enough ;good
-
enough (assign t (op square) (reg guess)) (assign t (op
-
) (reg t) (reg x)) (assign t (op abs) (reg t)) (test (op
<
) (reg t) (
const
0.001
)) (branch (label sqrt
-
done)) ;improve (assign t (op
/
) (reg x) (reg guess)) (assign t (op
+
) (reg guess) (reg t)) (assign guess (op
/
) (reg t) (
const
2.0
)) (
goto
(label good
-
enough)) sqrt
-
done)
在start之后，从寄存器guess中得到最后结果。
5.4
a)第一个是一个指数计算过程，用到了递归，因此需要引入continue寄存器来保存和恢复堆栈，实现与阶乘相似，如下
(controller
(assign
continue
(label expt
-
done)) expt
-
loop (test (op
=
) (reg n) (
const
0
)) (branch (label expt
-
base
-
case
)) ;;保存continue (save
continue
) (assign n (op
-
) (reg n) (
const
1
)) (assign
continue
(label after
-
expt)) (
goto
(label expt
-
loop)) after
-
expt ;;恢复continue (restore
continue
) (assign val (op
*
) (reg b) (reg val)) (
goto
(reg
continue
)) expt
-
base
-
case
(assign val (
const
1
)) (
goto
(reg
continue
)) expt
-
done (perform (op display) (reg val)))
b) 迭代型的递归计算过程，尾递归调用，因此不需要continue寄存器来保存和恢复堆栈，这道习题就是希望能分辨非尾递归和尾递归带来的寄存机器语言的区别
(controller (assign product (
const
1
)) (assign n (op read)) (assign b (op read)) (assign counter (reg n)) expt
-
iter
-
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
-
iter
-
loop)) expt
-
done (perform (op display) (reg product)))
5.5 手工模拟就算了，5.2节就可以机器模拟了
5.6 是有一个多余的save和一个多余的restore操作，请看注释：
( (assign
continue
(label fib
-
done)) fib
-
loop (test (op
<
) (reg n) (
const
2
)) (branch (label immediate
-
answer)) ;;compute fib(n
-
1
) (save
continue
) (assign
continue
(label after
-
fib
-
1
)) (save n) (assign n (op
-
) (reg n) (
const
1
)) (
goto
(label fib
-
loop)) after
-
fib
-
1
;;compute fib(n
-
2
) (restore n) ;这里多余，(restore
continue
) (assign n (op
-
) (reg n) (
const
2
)) ;这里多余，(save
continue
) (assign
continue
(label after
-
fib
-
2
)) (save val) ;;save fib(n
-
1
) (
goto
(label fib
-
loop)) after
-
fib
-
2
(assign n (reg val)) (restore val) (restore
continue
) (assign val (op
+
) (reg val) (reg n)) (
goto
(reg
continue
)) immediate
-
answer (assign val (reg n)) (
goto
(reg
continue
)) fib
-
done)
文章转自庄周梦蝶 ，原文发布时间2009-06-11
相关资源：敏捷开发V1.0.pptx
