转载

SICP 第五章总结

经过第四章元语言抽象的洗礼，我们已经能够深谙编译器内部的原理，核心就是 eval-apply 循环，只是说基于这个核心可以有各种延伸，像延迟求值、amb 不定选择求值、逻辑求值等等，有了这层的理解，我们应该能够透过各种花哨的语言糖，看出其本质来，像 Node.js 中的 Promise、 Python 中的 coroutine，都是 continuation 的一种应用而已。

但是，我们还无法解释子表达式的求值怎样返回一个值，以便送给使用这个值的表达式，也无法解释为什么有些递归过程能产生迭代型的计算过程，而另一些递归过程却生产递归型的计算。就其原因，是因为我们所实现的求值器是 Scheme 程序，它继承并利用了基础系统的控制结构。要想进一步理解 Scheme 的控制结构，必须转到更低的层面，研究更多细节，而这些，就是第五章的主要内容。

寄存器机器的设计

为了探讨底层的控制结构，本章基于传统计算机的一步一步操作，描述一些计算过程，这类计算机称为寄存器机器，它的主要功能就是 顺序的 执行一条条指令，操作一组存储单元。本章不涉及具体机器，还是研究一些 Scheme 过程，并考虑为每个过程设计一个特殊的寄存器机器。

第一步工作像是设计一种硬件体系结构，其中将：

开发一些机制支持重要程序结构，如递归，过程调用等
设计一种描述寄存器机器的语言
做一个 Scheme 程序来解释用这种语言描述的机器

寄存器机器包含 数据通路(寄存器和操作) 和确定操作顺序的 控制器 。书中以 gcd 算法为例介绍：

(define(gcda b) (if(=b0)  a (gcdb(remainera b))))

为了描述复杂的过程，书中采用如下的语言来描述寄存器机器：

(controller  test-b (test(op=)(rega)(const0)) (branch(labelgcd-done)) (assignt(oprem)(rega)(regb)) (assigna(regb)) (assignb(regt)) (goto(labeltest-b))  gcd-done)

子程序

直接带入更基本操作的结构，可能使控制器变得非常复杂，希望能够作出某种安排，维持机器的简单性，而且避免重复的结构，比如如果机器两次用GCD，最好公用一个 GCD 部件，这是可行的，因为任一时刻，只能进行进行一个 GCD 操作，只是输入输出的寄存器不一样而已。思路：

调用 GCD 代码前把一个寄存器(如 continue)设置为不同的值,在 GCD 代码的出口根据该寄存器跳到正确位置

具体代码与图示可参考： 2015-05-12_subroutes.md

采用堆栈实现递归

(define(factorialn) (if(=n1)  1 (*n(factorial(-n1)))))

表面看计算阶乘需要嵌套的无穷多部机器,但任何时刻只用一部。要想用同一机器完成所有计算,需要做好安排,在遇到子问题时中断当前计算,解决子问题后回到中断的原计算。注意:

进入子问题时的状态与处理原问题时不同(如 n 变成 n-1)
为了将来能继续中断的计算,必须保存当时状态(当时 n 的值)

控制问题:子程序结束后应该返回哪里？

continue 里保存返回位置,递归使用同一机器时也要用这个寄存器,给它赋了新值就会丢掉当时保存其中准备返回的位置
为了能正确返回,调用前也需要把 continue 的值入栈

阶乘算法的具体解释与图示可参考： 2016-05-16_recursion_stack.md

这里比较难理解的是 fib 算法，因为这里涉及到两次递归调用：

(define(fibn) (if(<n2)  n (+(fib(-n1)) (fib(-n2)))))  (controller (assigncontinue(labelfib-done)) fib-loop (test(op<)(regn)(const2)) (branch(labelimmediate-answer)) ;; set up to compute Fib(n-1) (savecontinue) (assign(continue(labelafterfib-n-1)) (saven); save old value of n (assignn(op-)(regn)(const1))); clobber n to n-1 (goto(labelfib-loop)); perform recursive call afterfib-n-1; upon return, val contains Fib(n-1) (restoren) (restorecontinue) ;; set up to compute Fib(n-2) (assignn(op-)(regn)(const2)) (savecontinue) (assigncontinue(labelafterfib-n-2)) (saveval); save Fib(n-1) (goto(labelfib-loop)) afterfib-n-2; upon return, val contains Fib(n-2) (assignn(regval)); n now contains Fib(n-2) (restoreval); val now contains Fib(n-1) (restorecontinue) (assignval(op+)(regval)(regn)); return to caller, answer is in val (goto(regcontinue)) immediate-answer (assignval(regn)); base case: Fib(n) = n (goto(regcontinue)) fib-done)  ;; afterfib-n-1 中先把 continue 释放，然后又保存起来，中间什么操作也没有

习题5.6 、习题5.11 对这一算法进行了分析，建议大家看看。