[Back]

Chapter 5

5.1 寄存器机器的设计

为了理解和解释程序运作的方式,我们抽象了很多模型,比如代换模型,环境模型和元循环模型。 然而这一切都建立在了Lisp最基本的控制结构基础上,为了理解这些基础的控制结构,我们就需要前进到更基础的层次,即一个硬件的顺序执行寄存器层面上。 尽管我们这样所涉及的很像是基本的机器语言,但是实际上我们所需要做的是抽象出这种顺序的机器阵列和指令,以期能求解一些通用的概念和问题。

我们可以使用数据通路来表示寄存器中的硬件和各种操作,一般地说,我们约定,矩形为寄存器,箭头为数据流向,而梯形为计算模块,圆作为检测模块,三角形代表了常量。

这种数据通路图和控制器图很适合来表示简单机器,但是对于更为复杂的大型程序,我们就需要尝试着以正文的形式给出控制器和数据通路的描述和信息。

接下来让我们考虑部件复用的情况,一旦我们需要重复地调用这些部件,就会显得非常不经济了。我们考虑使用将标号赋值到一个寻址寄存器的方法来处理调用时的返回位置。这边还出现了一个问题,当我们需要有多个子程序相互调用的时候,应该共享寄存器还是另外使用单独的寄存器?这个问题在递归中表现得尤为显著。 在处理递归问题的时候,我们需要采用一种被称为堆栈的数据结构来储存递归前状态,至于为什么不采取恢复的策略,一方面由于复杂性,另一方面,递归的参数可能有着不可恢复性。同时在确定返回位置的时候,我们就需要使用寻址寄存器的保存和恢复作为一种手段了。

 

5.2 一个寄存器机器模拟器

为了能够确实的了解寄存器机器的运行状况,我们显然不能手动模拟内容,一个有效的方法是书写一个scheme程序来模拟这些操作。

这里我们采用消息传递的思想来定义机器和寄存器.

实际上,我们还可以通过增加一些检测仪器和小模块来掌握寄存器机器的性能和表现测试,除了书上提到的对堆栈的监测外,以下是一些练习。

 

5.3 存储分配和废料收集

在这一节里,我们假定了我们能够在寄存器中实现Lisp的表结构,并分配和创建它们,由此就会使得我们的注意力转向了另一个重要的问题,如何使用自动化的存储分配方式,维持出来一个无限存储的假象。这里介绍一种被称为垃圾回收(废料收集)的技术。

DEF.57 地址算术 在计算机中,我们不仅需要将储存器的数据存到寄存器中,也需要将储存器的地址或者说位置存进来,以便能够在离散的存储器结构中维持一种连续存储的能力。这也是Lisp的表结构所依赖的一种算法。

这样的一种连续存储的结构被称为向量。 确定好一种带类型标志的指针后,我们就可以在向量中对应的下表存储信息了。 尽管这样,为了能高效地处理eq?过程,我们还需要创建一张对象表来储存解释器遇到的所有符号,这样,我们就可以用同一个指针来表示相同的符号了。

一个废料收集的有效思想是将存储器划分为两个部分,工作区和自由区,然后当工作区已满的时候,就追踪所有的car和cdr,把它们放到新的自由区,然后清空工作区,调换两个分区的角色。 这个废料收集的基本思想就是在一次dfs的遍历中完成对有用数据的标记和转移。

 

5.4 显式控制的求值器

在这一节里,我们需要将Scheme解释器实现为一个基本的寄存器机器。 我们有一个堆栈和七个寄存器 Exp env val continue proc argl unev

同样,这里会使用数据导向的工作来分派eval的表达式。 对于简单的数字变量和字符串,我们直接复制给val寄存器,而lambda表达式则利用了arglunev作为临时保存量,来包装好以后赋值给val。 对于过程应用,我们则需要递归的求出每个子表达式的值,这一过程中需要保存一系列寄存器的值。 实际上这里的不同处理方式决定了参数表的求值过程,如果我们采用了一种尾递归的策略,就可以完成自然的累计,加快argl的工作效率。 同样的,对序列的最后一个表达式的特殊处理使得我们的表达式可以自然地处理尾递归,因为这一过程并不会在堆栈中积累信息。这给了迭代计算重要的基础。

我们对求值模型的追求和精确在这里达到了一个终点,从代换模型到环境模型,再到元语言模型和现在的寄存器模型,我们解决了许多在之前含糊和无法解决的问题,包括赋值,过程应用,词法分析以及存储管理和参数调用等问题。