寄存器机器的计算.PDF

5. 寄存器机器的计算(1) 本书的最后一章讨论更底层的计算，以及从抽象层的程序（ Scheme 程序）到底层程序的翻译（编译） 本节课的内容： 寄存器机器 描述寄存器机器的计算过程 寄存器机器语言 子程序和递归带来的问题 寄存器机器语言的模拟器（解释器） 模拟器的实现 程序设计技术和方法 裘宗燕，2014-6-11 (1) 求值器的控制和寄存器机器 前面研究了计算（过程）和用Scheme 的过程描述计算的各方面问题， 提出了几个求值模型，解释过程的意义 代换模型 环境模型 元循环模型 元循环模型表现出求值过程的许多细节，但仍然有些遗漏，主要是没解 释Scheme 系统里的基本控制动作，如 求出子表达式的值之后如何把它送给使用值的表达式？ 为什么有些递归过程会产生迭代型计算过程（只需要常量空间）， 而另一些却产生递归型计算过程（需要线性以上的空间）？ 原因：求值器是Scheme 程序，它继承并利用了基础系统的结构 要进一步理解Scheme 求值器的控制，必须转到更低层面，研究更多 实现细节。最后一章的工作考虑这些问题 程序设计技术和方法 裘宗燕，2014-6-11 (2) 寄存器机器 下面基于常规计算机（寄存器机器）基本操作描述计算，寄存器机器的 功能是顺序地执行一条条指令，操作一组存储单元（寄存器） 典型的寄存器机器指令，就是把一个操作应用于几个寄存器的内容，并 把操作的结果存入某个寄存器 基于这种操作描述的计算过程就像典型的机器指令程序 这里不涉及具体机器，还是研究一些Scheme 过程 要考虑为每个过程设计一部特殊的寄存器机器 第一步工作像是设计一种硬件体系结构，其中将： 开发一些机制支持各种重要程序结构，如递归、过程调用等 设计一种描述寄存器机器的语言 做一个Scheme 程序来解释用这种语言描述的机器 这部机器中的多数操作都很简单，可以用简单的硬件执行 程序设计技术和方法 裘宗燕，2014-6-11 (3) 寄存器机器 为了实现Scheme 解释器，还需要考虑表结构的表示和处理 需要实现基本的表操作 实现作为运行基础的巧妙的存储管理机制 后面讨论有关的基础技术（可能简单介绍） 有了基本语言和存储管理机制之后，就可以做出一部机器，它能 实现前面的元循环解释器 而且为解释器的细节提供了清晰的模型 这一章的最后讨论和实现了一个编译器 把Scheme 语言程序翻译到这里的寄存器机器语言 还支持解释代码和编译代码之间的连接，支持动态编译等 由于时间关系，后面部分不讲了。有兴趣的同学自己阅读，有问题可 以给我发邮件，或以其他方式讨论 程序设计技术和方法 裘宗燕，2014-6-11 (4) 设计寄存器机器 寄存器 检测，其结果影 响控制器的活动 寄存器机器包含数据通路 （寄存器和操 作）和确定操作顺序的控制器 过程（以GCD 算法为例）的机器： (define (gcd a b) 把余数送入寄存 (if (= b 0) 器t 的按钮。受 a 控制器的控制 (gcd b (remainder a b)))) 常量， 执行这个算法的机器必须维护a