5.1 图就不画在机器上了，麻烦
5.2 用寄存器语言描述5.1题中的阶乘机器，加上了读取和打印,这里的解答全部在实际的寄存机器中验证过，但是仍然按照该节的表示法表示。
5.3 牛顿法求平方根，将这个过程转化为寄存器语言，第一个版本，假设good-enough?和improve都是基本过程，
第二个版本，展开good-enough?过程，
5.4
a)第一个是一个指数计算过程，用到了递归，因此需要引入continue寄存器来保存和恢复堆栈，实现与阶乘相似，如下
b) 迭代型的递归计算过程，尾递归调用，因此不需要continue寄存器来保存和恢复堆栈，这道习题就是希望能分辨非尾递归和尾递归带来的寄存机器语言的区别
5.5 手工模拟就算了，5.2节就可以机器模拟了
5.6 是有一个多余的save和一个多余的restore操作，请看注释：
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)))
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)
(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过程，
(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)
;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中得到最后结果。
(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)
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)))
(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)))
(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)
(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
