H2003032104_贺鹏飞_Scheme解释程序的实现

分类号：TP314 U D C：D10621-408-(2007)5779-0密 级：公开 编 号：2003032104成都信息工程学院学位论文Scheme解释程序的实现论文作者姓名：贺鹏飞申请学位专业：网络工程申请学位类别：工学学士指导教师姓名（职称）：韩斌（副教授）论文提交日期：2007年06月09日Scheme解释程序的实现摘 要Scheme是一种函数式编程语言，是第一个完全支持词法作用域、第一级过程以及继续的LISP方言。它语法简洁但功能强大，而且非常优雅，具有数学的美感，同时蕴含着丰富的数学理论和程序设计技术。Scheme具有极高的开发效率，并且相当容易学习，它能使学习它的人从一开始就将注意力放到编程思想上，而不是停滞在学习繁琐的语法上。在Scheme解释程序的设计中，充分采用了模块化的设计思想，首先将解释程序的整体结构与Scheme的核心内容理清，然后再设计解释程序的整体架构，并定义好各模块的结构和相关模块之间的接口，之后再逐模块地进行具体的代码实现工作。整个解释器的核心是一个虚拟的寄存器机器，及其支持的一套基本指令集。该寄存器机器还要基于向量模型来管理内存，并实现垃圾回收机制。Scheme的源代码将被词法分析器解析成内部表结构来表示，再传入操作的解释模块中，转化为仅由基本指令组成的执行过程，在寄存器机器中执行。关键词：解释程序；Scheme；垃圾回收；虚拟的寄存器机器Implementation of the Scheme InterpreterAbstractScheme, a function programming language, is the first dialect of LISP to fully support lexical scoping, first-class procedures, and continuations. With perfect design it is very simple, but powerful. And many programming technologies and mathematics theories can be found in it. Programming in scheme, the development efficiency can be enhanced enormously. However, it is very easy to master and use scheme, because its syntax could be learned quickly.In the scheme interpreter design, the module design concept has been used fully. After the content of scheme and the structure of interpreter are mastered, the scheme interpreters structure is designed. And then the interfaces between modules are defined. After all of above are done, these modules and interfaces are implemented one by one.The core of the scheme interpreter is the Virtual Register Machine with a set of supported basic instructions. In the Virtual Register Machine, the memory is managed through vector model with the garbage collection facility. After analyzed by the lexical analyzer, Scheme source codes are parsed into internal list structures. Then these list structures are converted into the basic instructions by evaluator module. And these instructions are executed through registers in the Virtual Register Machine.Key words: Interpreter; Scheme; Garbage Collection; Virtual Register Machine目 录论文总页数：24页1 引言11.1 课题背景11.2 研究意义11.3 研究方法12 Scheme语言22.1 发展历史与现状22.2 Scheme语言介绍22.3 Scheme的特点33 相关理论基础34 解释程序的整体结构34.1 词法分析器44.2 类型系统44.3 循环求值器44.4 虚拟的寄存器机器54.5 内存管理与垃圾回收55 解释程序的实现65.1 类型系统65.2 词法分析75.3 表达式求值的环境模型75.3.1 环境模型75.3.2 环境操作95.3.3过程应用的环境模型95.3.4 环境模型的实现105.4 尾递归115.5 虚拟的寄存器机器135.5.1 寄存器145.5.2 存储模型155.5.3 基本表操作的实现165.5.4 停止并复制垃圾回收算法175.5.5 虚拟的寄存器机器的实现185.6 表达式求值过程186 测试结果196.1 测试尾递归196.2 测试正确性与效率20结 论21参考文献22致 谢23声 明241 引言1.1 课题背景Scheme是一种函数式编程语言，是LISP的一种方言。它语法简洁但功能强大，Scheme的设计理念是：程序语言不是拿来“学”的，而是拿来“用”的。Scheme是非常优雅的，它具有数学的美感，蕴含着丰富的数学理论和程序设计技术。Scheme诞生后，由于其具有所有LISP的优点，而且简洁、强大、稳定、特别适合用于描述算法，以至于Scheme在教育界被广泛的使用，新一代优秀的计算机科学家中有很多人的“母语”就是Scheme。我学习它可以更深入的体会程序设计的数学原理，对以前所学的知识进行一次融会贯通。实现一个解释程序，要有扎实的基础和编程能力，也要求对编程语言有更高层次的理解。选择它作为毕业设计，可以很好的考验我的基础知识和动手能力。1.2 研究意义模块化是成功的程序设计的关键。以提高生产力为目标的程序语言，必须良好地支持模块化程序设计。但是，新的作用域规则和分块编译的技巧是不够的“模块化”不仅仅意味着把程序分成几个的“模块”，还需要能把它们有效的组合起来。我们分解程序的能力直接取决于将解决方案粘在一起的能力。为了协助模块化程序设计，程序语言必须提供优良的黏合剂。函数式程序语言提供了两种新的黏合剂高阶函数与惰性求值，而Scheme就提供了这些。Scheme中的过程是一级对象，可以动态创建，可以存储于数据结构中，可以作为过程的结果返回，等等。研究Scheme，就可以从实践的角度来理解函数式编程，来体会模块化技术的极致，以及函数式编程带来的开发效率的提升。Scheme是一门优雅的语言，并带有极高的开发效率，而且相当容易学习，它能使学习它的人从一开始就将注意力放到编程的思想上，而不会停滞在学习繁琐的语法上慢慢地耗尽耐心。作为国外大学计算机科学的一门必修课，我认为我们也应该把它作为学习计算机科学的起始点。这也是我的初衷。1.3 研究方法在设计中，充分采用模块化的设计思想，先将解释程序的整体结构与Scheme的核心内容理清，并设计好各模块的结构和相关模块之间的接口。之后，再逐步进行具体的实现。整个解释器的核心是一个寄存器机器，以及其支持的一套基本指令集。通过扩展，将Scheme的源程序解释到这一套基本指令集上。这个寄存器机器还要管理内存，并实现垃圾回收机制。Scheme的源代码将被词法分析器解析成内部表结构来表示，再传入操作的解释模块中，转化为仅由基本指令组成的执行过程，在寄存器机器中执行。2 Scheme语言2.1 发展历史与现状Scheme的前身是LISP，它们都是诞生在MIT人工智能实验室的语言。LISP在程序语言的族谱上，辈份仅次于Fortran，是第二古老的语言。LISP由图灵奖获得者John McCarthy发明。LISP重要的特征就是：第一，基于lambda演算的计算模型；第二，加上list processing，这也是LISP名称的由来；第三，直接在抽象语法里面工作，这点非常特别。两个更年轻的计算机科学家Guy Steele和他的老师Gerald Sussman合作对古典LISP做了两个重要改进。一是把LISP从动态作用域（dynamic scope）变成了词法作用域（lexical scope）。后来Steele成为Common Lisp设计的主力，Common Lisp把Scheme的词法作用域和其它一些由Scheme所创造的特征，都加入到主流LISP语言当中，使动态作用域终于成为了历史。Steele和Sussman做的另一个主要改进是把continuation概念引入到程序语言里面。这样，一门新的程序语言就此诞生。他们按照人工智能实验室的传统，把它命名为Scheme。Steele和Sussman发明了Scheme以后，写了份Report on Scheme。后来经过修改，又发布了Revised Report on Scheme，这样不停的Revise下去，这一系列的Report被依次命名为R2RS、R3RS、R4RS和目前使用的R5RS1，现在R6RS正在制订过程中，并且已经于今年5月22号公布了草稿R5.93RS。现在，Scheme正伴随着函数式编程思想的复兴而复兴，由于其优良的设计，以及其快速的开发能力，其应用也不再局限于人工智能领域了，而是走向了更广泛的应用。2.2 Scheme语言介绍Scheme是一门高级通用编程语言，支持基于数据结构的操作，如字符串、表、数组，以及基本数据类型的操作，如数字和字符。Scheme相当易于学习，因为它只基于少量语法形式和语义概念。Scheme里面的所有对象都是基于两种基本结构构建起来的：原子：有9种类型的基本数据，包括数字、字符、字符串、点对、过程、端口、布尔、符号、向量。表：由原子或空表组合而成的表，其中空表是一种特殊的表。Scheme语言只有6种基本语法结构，即变量引用、常量表达式、过程调用、lambda、条件表达式和赋值。它的最基本的程序结构是递归，标准规定Scheme的实现必须支持严格尾递归，这一机制使得迭代（循环）可以用递归来表示，并且可以在常量空间内执行。2.3 Scheme的特点Scheme的一个特性是程序与数据的一致性，既可以将程序当作数据来处理，也可以将数据作为程序来执行，它们不仅仅在形式上具有一致性，其本质也是相同的，即都是Scheme对象。Scheme中，不管程序还是数据，都用S-表达式来表示，其基本的数据结构是表。Scheme采用的是隐式类型，而不是显式类型，类型与对象关联，而不是与变量关联。在Scheme中创建的所有对象，都拥有无限的生存期，它们永远不会被销毁。由于当前的计算机存储器只有有限的容量，因此Scheme的实现必须要使用自动存储分配功能，以维护一种无限存储器的假象。Scheme标准规定，如果能证明某个对象无论如何都不会与未来的任何计算发生关联，就可以回收该对象占据的空间。3 相关理论基础该Scheme解释程序的开发环境是Linux下的Emacs编辑器，所使用的开发语言是C+与Scheme，结合使用gdb进行程序的调试、使用subversion进行源代码的版本管理、使用makefile来组织代码文件。现在已经有大量优秀的Scheme解释程序，而且大部分是开源软件，例如GNU Guile、MIT Scheme等等，这些解释程序的开发语言多种多样，像C、C+、Scheme、Java等等，它们遵循的大多都是R5RS1标准。但由于它们都是以应用为目的的解释程序，通常都将效率与空间放在第一位，这就导致它们的程序结构比较复杂。本次毕业设计的目的是要了解Scheme解释程序的结构，以及对编程语言的本质的更深入的理解，因此就要避免复杂的设计。本次毕业设计的主要参考为SICP3，解释程序的大部分设计模型都来自本书中（书中的解释程序是用Scheme本身写的）。该程序所涉及到的内容主要有词法分析、求值的环境模型、垃圾回收机制和虚拟的寄存器机器模型。4 解释程序的整体结构整个解释器包含几大部分，首先是词法分析，将Scheme源程序代码表示为内部表示形式，即表结构；然后将表结构形式的源程序传到求值器中，以对表达式进行求值。在求值器对表达式求值的过程中，要基于虚拟的寄存器机器来做运算，所有的运算操作都是在寄存器中完成的。而寄存器机器又封装了对内存的组织与管理，并实现了垃圾回收机制来释放不会再被使用的Scheme对象。解释器的整体结构图见图1。图1 解释器的整体结构4.1 词法分析器词法分析是将源程序中的各种成分拆开，并解析成一个一个的基本元素，识别为原子或表，相应的创建每个基本元素对象，而该对象就含有元素的类型信息。再将这些对象组织成一张表结构的形式，形成代码的内部表示，以便在循环求值器中对其求值。4.2 类型系统在创建基本元素对应的对象时，该对象中要含有类型信息。类型系统就定义了Scheme语言中的9种数据类型，并将其嵌入到对象中。这样，在词法分析过程中只要创建相应类型的Scheme对象即可。该类型系统同时决定着Scheme源程序的内部表示的数据结构。4.3 循环求值器求值器对Scheme程序进行计算，它的计算方式要与Scheme程序的语义吻合。该求值器包含两个部分：1、在求值一个组合式时，首先求值其中的子表达式，其中第一个子表达式的值就是运算符，而后将运算符子表达式的值作用于运算对象子表达式的值；2、将一个复合过程应用于一级实际参数，就是在一个新的环境里求值这个过程的体。构造这一环境的方式就是用一个框架扩充该过程对象的环境部分，框架中包含的是这个过程的各个形式参数与这一过程应用的各个实际参数的约束，这就是求值的环境模型。上面两条规则描述了求值过程的基本循环，也就是它的核心部分。在这一循环中，表达式在环境中的求值被归约到过程对实际参数的应用，而这种应用又被归约到新的表达式在新的环境中的求值，如此下去，直到我们下降到符号（或称变量，其值可以在环境中找到）或基本内置过程（它们由解释程序实现）。这一求值循环体现为求值器里的两个关键操作“求值”和“应用”的相互作用，见图2。图2 揭示计算机语言本质的求值应用循环4.4 虚拟的寄存器机器在解释程序中，实现了一个虚拟的寄存器机器，就像真实的计算机一样，它也包含了一组寄存器、一块存储区域、以及一些类似汇编的基本操作。这一套基本操作扮演着机器的基本指令集的角色，它们执行的操作只是简单的从内存和寄存器中互相交换数据。Scheme代码的计算全都放在这部寄存器机器中进行。在寄存器机器中的Scheme代码是内部表结构形式，因此它们所操作的对象就是一张表，所执行的操作就是对这张表进行一些修改，由此来完成Scheme代码的计算。4.5 内存管理与垃圾回收Scheme程序的基本结构是表结构，为了使表结构适合创建和修改，把内存结构重新组织为基于向量的，因此所有的表操作，到最底层都归结为对向量形式的内存单元的操作。为封装这一细节，便创建了内存管理模块。按Scheme标准规定来实现解释程序的话，就需要有无穷数量的存储器，而这是不可能的，因此就需要使用垃圾回收机制来维护一种无穷存储器的假象。考虑到Scheme本身的表结构，以及实现的复杂性，这里采用相对简单但却有优势的一种垃圾回收算法停止并复制算法。其基本思想就是将存储器分成两半：“工作存储区”和“自由存储区”。当需要创建对象时，就从工作存储区中分配它们。当工作存储区满的时候就执行垃圾回收操作，将工作存储区中的有用对象复制到自由存储区中，并形成连续的位置。然后再交换两个存储区的角色，继续进行下去。在支持虚拟存储器的系统中，由于该算法是一种紧缩型垃圾回收算法，使得所有数据都被移到一片连续的存储位置中，因此可以避免很多换页操作。5 解释程序的实现5.1 类型系统原子（atom）是Scheme的基本单位，它可以是基本数据、空表（null）和由原子或空表组成的表。Scheme中有9种互不相交数据类型，它们是布尔(boolean)、点对(pair)、符号(symbol)、数值(number)、字符(char)、字符串(string)、向量(vector)、端口(port) 和过程(procedure)类型。空表是一个隶属于其自身类型的特殊对象，它不能属于上述任何一种类型。互不相交是指一个对象能且只能属于其中一个类型。Scheme中对布尔值的规定是这样的，只有该对象是布尔类型并且值为假时才为假，否则总为真。这也就是说Scheme中的任何值都可以作为布尔值参与条件判断。在条件判断中，除了#f以外，所有值都被视为真。Scheme是隐式类型语言，对象的类型信息是与对象的值相关联，而不是与对象所绑定的变量相关联。因此，类型系统设计为将对象的类型信息包含在对象结构中，具体的类层次实现请见图3。图3 类型系统的类层次结构在实现中，将Scheme对象分为简单对象和复合对象。简单对象直接用值表示，如整数、字符、布尔等；而复合对象用一个指针来表示，该指针指向内存中该复合对象的起始位置。复合对象全部用表结构来表示，如字符串是字符的表，向量是原子的表，过程是参数、环境和过程体的表等等。在Scheme中，过程也是对象，需要用一个原子对象来表示；Scheme的语法也有过程的特点，也是一个对象。在求值环境中，只是将一些符号绑定到指定的过程对象或语法对象，用户代码中完全可以将这些符号绑定到其它的任何对象，例如初始环境中语法关键字define绑定到语法对象OT_DEFINE，运算符+绑定到过程对象OT_PLUS，但求值语句(set! define 23)和(set! + #S)后，define就被绑定到数字对象23、+被绑定到字符S了。由于过程和语法的相似性，在实现中将语法也表示为过程对象。在对过程调用求值时，通过识别过程的名称，来调用相应的内部C+函数执行运算操作。这里的过程名称用枚举来定义，过程定义为模板类，相应名称的过程实现为相应的偏特化模板类。例如lambda过程的名称为OT_LAMBDA，相应的偏特化模板类定义为：template class PrimitiveProcedure；相应的还有参数个数限制的模板类定义，偏特化版本为：template class Arity；具体的操作执行过程就在这里实现。5.2 词法分析词法分析就是要将Scheme源程序中的原子都识别出来，并过滤掉空白和注释，将源程序组织为内部数据结构来表示。图4所示就是词法分析的主要流程图。5.3 表达式求值的环境模型表达式求值模型有两种：代换模型和环境模型。函数式程序设计中，可以采用代换模型。因为以同样的参数对同一过程的两次求值一定产生出同样的结果，可以认为过程是在计算数学函数。代换模型是具有漂亮的数学性质的简单模型。但由于Scheme并不是纯函数式编程语言，而且Scheme实现的是词法作用域，因此不能使用代换模型。在实现中采用环境模型作为求值模型。5.3.1 环境模型一个环境（environment）就是框架（frame）的一个序列，每个框架是包含着一些约束（binding）的表（可能为空），这些约束将一些变量名字关联于对应的值（在一个框架里，任何变量至多只能有一个约束）。每个框架还包含着一个指针，指向这一框架的外围环境（enclosing environment）。一个变量（variable）相对于某个特定环境的值（value），也就是在这一环境中，包含着该变量的第一个框架里这个变量的约束值。如果在序列中并不存在这一变量的约束，那么我们就说该变量在该特定环境中是无约束（unbound）的。如果在当前框架中找不到某个变量的约束，则应转到其外围环境中去查找。这样就实现了词法作用域。图4 词法分析流程图环境对于求值过程是至关重要的，因为它确定了表达式求值的上下文。在解释程序开始运行后，会初始化一个全局环境，在这个环境中包含着一个框架，其中包含着所有关联于基本内置过程的绑定。只有在这个环境存在的情况下，一个表达式才有意义，如(+ 1 1)这样的表达式，其行为要取决于符号+绑定到哪一个操作，在全局环境中它是与加法操作绑定起来的，但用户完全可以修改这个绑定，使它具有其它的意义。5.3.2 环境操作Scheme中有两个用来操作环境的语法：define和set!。1、define的行为define是作用于框架的，用define定义一个符号，就是在当前环境框架里建立一个约束，如果在当前框架中已经有了对这一变量的约束，那么约束就会改变。它不会去外围环境查找该符号的约束。2、set!的行为set!是作用于环境的，在某个环境里求值表达式(set! )，要求我们首先在环境中确定有关变量的约束位置，而后再修改这个约束，使之表示新值。这也就是说，首先需要找到包含这个变量的约束的第一个框架，而后修改这一框架。如果该变量在环境中没有约束，set!将报告一个错误。例如，下面的代码将变量square绑定到复合过程对象：(define square (lambda (x) (* x x)这里的复合过程对象是由lambda表达式创建的，它的内部结构是一个表，表中包含该过程的参数、过程体和它所处的环境。在对上面这一表达式求值后，当前的环境中就多了一个变量绑定，如图5所示。图5 在全局环境中求值表达式而产生的环境结构5.3.3过程应用的环境模型在求值(square 5)的时候，首先会扩展当前环境，并创建参数x与5的绑定添加到新的环境E1中，然后在这个环境中求值square的过程体，如图6。图6 在全局环境中求值(square 5)创建出的环境关于解释程序如何求值过程应用，可以总结为下面两条规则：1、将一个过程对象应用于一集实际参数，将构造出一个新框架，其中将过程的形式参数约束到调用时的实际参数，而后在构造起的这一新环境的上下文中求值过程体。这个新框架的外围环境就是被应用的那个过程对象所处的环境。2、相对于一个给定环境求值一个lambda表达式，将创建起一个过程对象，这个过程对象是一个序对，由该lambda表达式的正文和一个指向环境的指针组成，这一指针指向的就是创建这个过程对象时的环境。5.3.4 环境模型的实现环境模型需要对外提供一些操作接口如下：1、查找变量的值返回此环境中相应变量的约束值，若没有该变量的约束就抛出一个错误。2、扩展环境返回一个新环境，这个环境中包含了一个新的空的框架，而其外围环境就是此环境。3、定义变量（添加约束）在环境的第一个框架里加入一个新的约束，它关联起给定的变量和值。如果第一个框架中已经有该变量的约束，则修改它。4、修改变量修改变量在环境里的约束，使得该变量约束到给定的值。如果没有这一变量的约束就抛出一个错误。在实现中，将环境表示为框架的表，框架表示为约束的表，约束表示为变量与值的点对。环境的基本操作有在当前框架中添加一个变量和值的约束；在整个环境中更改一个变量的约束值；在指定框架中查找某个变量的约束；在整个环境中查找某个变量的约束。上面的接口都是基于这几个基本操作来实现的。由于环境是用表来表示的，环境的基本操作都要用基本表操作来实现。因为所有的表操作都要基于寄存器来进行，所以将环境操作实现为寄存器机器的一部分，具体请参考“虚拟的寄存器机器”的一节。5.4 尾递归Scheme语言的一个重要特性是尾递归，这也是本次设计的一个重点。R5RS1标准规定，Scheme实现必须是严格尾递归的，即必须支持尾递归。直观上讲，尾递归使得迭代式的递归调用不需要任何额外的存储空间。下面是用Scheme实现的求幂运算，第一个实现为递归式，如下：; 求幂的递归版本; bn=b*b(n-1); b0=1(define expt (lambda (b n) (if (= n 0) 1 (* b (expt b (- n 1)用该版本对表达式(expt 2 5)求值的过程如下：(expt 2 5)(* 2 (expt 2 4)(* 2 (* 2 (expt 2 3)(* 2 (* 2 (* 2 (expt 2 2)(* 2 (* 2 (* 2 (* 2 (expt 2 1)(* 2 (* 2 (* 2 (* 2 2)(* 2 (* 2 (* 2 4)(* 2 (* 2 8)(* 2 16)32第二个实现为迭代式，如下：; 求幂的迭代版本(define expt (lambda (b n) (define expt-iter (lambda (b n result) (if (= n 0) result (expt-iter b (- n 1) (* b result) (expt-iter b n 1)其对表达式(expt 2 5)求值的过程如下：(expt 2 5)(expt-iter 2 5 1)(expt-iter 2 4 2)(expt-iter 2 3 4)(expt-iter 2 2 8)(expt-iter 2 1 16)(expt-iter 2 0 32)32可以看出，递归版本需要在调用过程中保存变量b的值，因此其空间需求与递归深度有关，而迭代版本则不需要任何额外的空间，它只需简单的将新的参数重新应用到自身即可。尾递归的作用巨大，但是实现却是相当简单。对参数、表达式序列中的最后一个表达式作特殊处理，即恢复以前保存的寄存器的值，不用再保存任何寄存器，然后对这最后一个表达式求值即可。这样，就相当于直接跳转到最后一个表达式中。下面是求值表达式序列的相关代码，尾递归就是在这里实现的。template struct Operation void operator() (Machine &pMachine) / 从R_UNEV取出第一个表达式，准备求值 pMachine.car (R_EXP, R_UNEV); / 取出剩余的表达式 pMachine.cdr (R_UNEV, R_UNEV); bool islast=pMachine.reg (R_UNEV).isNull().isTrue(); if (islast) / 求值最后一个表达式 /pMachine.restore (R_CONTINUE); Atom last=Atom:makePrimOp (OT_EVAL_SEQUENCE_END); pMachine.assign (R_CONTINUE,last); else / 保存起剩余表达式和环境 pMachine.save (R_UNEV); pMachine.save (R_ENV); / 设置求值后的返回地方 Atom seq=Atom:makePrimOp (OT_EVAL_SEQUENCE_LOOP); pMachine.assign (R_CONTINUE,seq); ;template struct Operation void operator() (Machine &pMachine) / 恢复环境和剩余表达式 pMachine.restore (R_ENV); pMachine.restore (R_UNEV); Atom seq=Atom:makePrimOp (OT_EVAL_SEQUENCE); pMachine.assign (R_EXP,seq); ;template struct Operation void operator() (Machine &pMachine) / 恢复环境 pMachine.restore (R_ENV); / 直接返回 pMachine.restore (R_EXP); / CONTINUE ;5.5 虚拟的寄存器机器虚拟的寄存器机器包含了一组寄存器和一块存储区域，以及一组基本操作，其逻辑结构如图7所示。图7 虚拟的寄存器机器的逻辑结构5.5.1 寄存器在实现中的寄存器机器中包含七个寄存器：exp、env、val、continue、proc、argl和unev。exp用于保存被求值的表达式，env里保存着这一求值进行所有的环境。在求值结束时，val里包含着在指定环境里求值表达式得到的结果。continue保存求值完当前表达式后将要被求值的表达式，类似于返回地址，用于实现递归。寄存器proc、argl和unev用在求值组合式的时候。proc用于保存当前求值表达式的操作符，argl中积累对运算对象（操作数）求值的结果，unev在求值组合式时用于保存未被求值的参数，在求值表达式序列时用于保存未被求值的表达式。在求值lambda表达式（即创建函数对象）时，令unev保存参数列表，exp保存函数体代码序列，env保存当前环境，然后创建函数对象(unev exp env)，并保存到val中。求值过程应用（即组合式）时，首先求值运算符以产生出一个过程，并将它移入proc寄存器。若有运算对象，则需要先保存proc寄存器，然后依次求值运算对象，并将结果积累到argl中。在求值时，将参数表保存到unev中，实现参数已经在argl中，并由此创建起新的框架，以过程所保存的环境作为外围框架，并将整个环境保存到env中，然后将过程体保存到unev中，并依次对其中的表达式求值。寄存器机器中还包含一个特殊的寄存器栈，它和一组栈操作一起，用来保存和恢复其它寄存器的值。栈也用表结构来表示，入栈操作即向表中添加一个表头，出栈操作即取表尾，其所占的存储空间在堆中，与其它对象放在一起。寄存器机器中定义了下面几个操作来操作寄存器和栈：1、获取寄存器的值Atom reg (Register r)；2、对寄存器赋值void assign (Register r, Atom pValue)；3、从一个寄存器赋值到另一个寄存器void assign (Register r1, Register r2)；4、保存寄存器的值到栈中void save (Register r)；5、从栈中恢复一个值到寄存器中void restore (Register r)；6、初始化栈，将其置为空void clear ()。5.5.2 存储模型寄存器机器中还有一块称为堆的内存区域，它对应于计算机的内存。为了模拟计算机的存储器，设计中采用向量数据结构来组织起内存的单元，每个单元对应于原子对象，在类型系统设计中使得每一个Scheme对象大小都一致，因此这种组织方式简单而方便。堆中的原子通过向量下标来访问，因为将下标称为指针，复合对象就是通过指针连接在一起的。为实现表结构，设计中将内存划分为两个向量，the-cars和the-cdrs，它们分别保存序对的两个元素。将序对用指针连接起来，就可以表示表结构。表(1 2) 3 4)的抽象数据结构和在存储器中的表示如图8。在图8中，指针对象用p表示，数字用n表示，空表用nil表示。表(1 2) 3 4)写成点对的形式即为(1 . (2 . () . (3 . (4 . ()，它与表的抽象数据结构表示相对应。图8 表(1 2) 3 4)的抽象数据结构和在存储器中的表示存储模型将存储器抽象为向量，相应的也封装了基本向量操作，即对向量的某一个进行存取的操作。堆实现是基于存储模型的，它将存储器划分为四个相等大小的区域，其中两个用于工作存储区的the-cars和the-cdrs，另外两个作为自由存储区的the-cars和the-cdrs。在堆中，基于向量操作，实现了无垃圾回收机制的基本表操作，用于在寄存器机器中实现带垃圾回收机制的基本表操作。存储模型和堆的具体实现见图9。图9 存储模型的实现5.5.3 基本表操作的实现Scheme中的基本表操作有5个，分别是创建点对、获取及设置点对的第一个元素、获取及设置取点对的第二个元素。有了堆中表操作的支持，在寄存器中的实现将非常简单，只要将检测存储空间是否足够和执行垃圾回收操作封装起来即可。从存储模型中可以看出，创建点对就是分别从the-cars和the-cdrs中分配一个元素，用来存储点对的car和cdr，获取及设置点对的内容就是获取和设置向量中相应位置的值。但是，寄存器机器中的表操作必须是基于寄存器来操作的，这是由垃圾回收机制决定的。寄存器机器中的基本表操作如下：1、根据两个寄存器的值创建点对，并保存到第三个寄存器中void cons (Register val, Register car, Register cdr)；2、获取寄存器中保存的点对的第一个元素，并保存到指定寄存器中void car (Register val, Register pValue)；3、获取寄存器中保存的点对的第二个元素，并保存到指定寄存器中void cdr (Register val, Register pValue)；4、将寄存器中保存的点对的第一个元素设置为给定寄存器中的值void setCar (Register pair, Register val)；5、将寄存器中保存的点对的第二个元素设置为给定寄存器中的值void setCdr (Register pair, Register val)。5.5.4 停止并复制垃圾回收算法在程序运行过程中，创建一个新的对象时，若内存不足便会引发垃圾回收，此时程序是处于被挂起的状态。在垃圾回收完毕并仍有可用内存时，程序才会重新恢复运行。在垃圾回收进行之前，需要先将寄存器机器中的所有寄存器都收集起来，在实现中是在内存的末尾预留8个寄存器的空间，将8个寄存器的内容都保存在这些空间中，将它们连成表，并称该表为root。在垃圾回收过程中要维护两个指针，free和scan，它们都被初始化为新存储区的开始位置。在算法开始时，将root所指向的点对拷贝到新存储区的开始位置，free指针的值被加1。此外，还要将该点对的car设置为破碎的心（broken heart）标记，说明该位置的内容已经移走，并将cdr设置为新位置的指针，称之为前向指针（forwarding pointer）。接下来垃圾回收就进入了基本循环部分。在这个算法的每一步，扫描指针scan指向的是一个本身已经被移入新存储区的对象，但它的car和cdr指针仍然指向旧存储区里的对象。现在要重新分配这样的被指对象，并相应的增加scan指针的值。要重新分配一个对象，首先要检查它是否已经被移走，即看其car域是否存放着一个破碎的心标记。若该对象还没有移走，就将它复制到free所指的位置，更新free，在这个对象的原位置设置破碎的心标志和前向指针，并更新指向这个对象的指针，使其指向新的位置。如果这一对象已经移走，那么就利用它的前向指针（即cdr域）找到其新的位置，并替换正被扫描的点对中的指针。所有可访问的对象都完成了移动和扫描后，scan指针将超过free指针，复制过程就结束了。然后再从root所指向的表中（现在已经在新存储区）依次取出元素，恢复到相应的寄存器中，以恢复垃圾回收前的运行状态。至此，整个垃圾回收操作就完成了。采用停止并复制技术可以极大地降低内存分配的开销，因为检查空间是否足够只需要做简单的指针比较；获取新内存可以简单地通过递增自由空间指针free来实现；由于活动数据缩并地排列在另一块内存区域的开始位置，内存碎片问题也不复存在。但停止并复制垃圾回收算法最直接的代价就是要使用两块内存区域，直观上讲这使得它比其它算法更耗内存，但支持虚拟存储器的系统会将不活动的半区换出到辅助存储器中，这在一定程度上抵消了它的这一缺陷。5.5.5 虚拟的寄存器机器的实现虚拟的寄存器机器模型的具体实现如图10所示。在寄存器机器中封装了寄存器操作、栈、环境操作、基本表操作、相等谓词比较等内容，整个解释程序都是基于该寄存器机器来实现的。5.6 表达式求值过程初始时将继续设置为结束对象，并在初始全局环境中加入一些标准语法和过程，如lambda语法、if语法、基本表操作、算术运算符操作、字符串操作等等。从输入流中读取一条Scheme表达式，并进行词法分析，转换为内部表示结构。然后将表达式赋给寄存器机器的exp寄存器，并进入循环求值过程。求值过程中首先判断表达式的类型，然后再根据类型执行相应的过程。在对过程调用进行求值时，先求值其第一个原子，即运算符。具体过程为保存表达式剩余元素，并保存继续和环境，将第一个原子赋给寄存器exp，并再次进入求值循环中对其求值；求值结束后，将值保存到proc寄存器中，并继续求值后继原子，即参数，直到所有参数都求值完成后，调用proc寄存器中的过程，根据参数进行运算，并将结果保存到val寄存器中。到此，完成了一条表达式的求值，然后将continue寄存器的值赋给exp，求值下一条表达式。直到exp的值为结束对象时，退出求值循环过程。具体细节不在此一一列出了，请参见程序代码中的相应实现部分。图10 虚拟的寄存器机器的类图6 测试结果6.1 测试尾递归尾递归的测试程序是在普通过程中加入记录栈深度的操作，下面是求fibonacci数列的过程，前者为普通递归方式实现，后者为迭代方式实现。; 普通递归方式(define fibonacci (lambda (n) (define fib (lambda (i) (if(= i 0) 0 (if (= i 1) 1 (+ (fib (- i 1) (fib (- i 2) (fib n); 迭代方式(define fibonacci-iter (lambda (n) (define fib (lambda (i a1 a2) (if (= i 1) a1 (fib (- i 1) (+ a1 a2) a1) (if (= n 0) 0 (fib n 1 0)基于上面和第8节求幂程序的定义，在解释程序中分别测试求2的7次幂和fibonacci数列第5项的值，表达式为(expt 2 7)、(expt-iter 2 7 1)和(fibonacci 5)、(fibonacci-iter 5)，求值过程中栈深度记录如下：(expt 2 7) = (0 16 21 26 31 36 41 46 51)(expt-iter 2 7 1) = (0 16 18 20 22 24 26 28 30)(fibonacci 5) = (0 18 25 32 39 46 53 60 67 74 72 65 58 65 63 51 58 65 63 56 44 51 58 65 63 56 49 56 54 37 44 51 58 65 63 56 18 25 32 39 46 44 37 30 37 35 23 30 37 35 28)(fibonacci-iter 5) = (0 18 20 22 24 26)从结果中可以看出迭代方式的增长阶总为2，非迭代方式的增长阶分别为5和7，说明尾递归确实降低了递归调用对空间的需求。但由于实现不很完善，导致栈中仍然要保存少量信息，但与非尾递归方式的调用相比，已经降低了一个级别。6.2 测试正确性与效率为了充分测试解释程序的正确性，用Scheme编写了一个Huffman编码与解码的代码，实现了对给定的符号表，统计出它的词频，并构建Huffman树，对符号表进行编码，以及从编码中解码出原符号表等功能，下面是详细的实现情况。Huffman编码与解码程序实现的功能是对给定的符号表进行编码与解码，主要操作有：1、根据符号表生成符号频度表；2、根据符号频度表生成相应的Huffman树；3、按照指定的Huffman树，对符号表进行编码，生成0/1编码表；4、按照指定的Huffman树，对0/1编码表进行解码，还原出符号表。通过在该解释程序中多次运行测试，以及与在GNU Guile等其它