104_Scheme解释程序

3 相关理论基础
该Scheme解释程序的开发环境是Linux下的Emacs编辑器，所使用的开发语言是C++与Scheme，结合使用gdb进行程序的调试、使用subversion进行源代码的版本管理、使用makefile来组织代码文件。
现在已经有大量优秀的Scheme解释程序，而且大部分是开源软件，例如GNU Guile、MIT Scheme等等，这些解释程序的开发语言多种多样，像C、C++、Scheme、Java等等，它们遵循的大多都是R5RS[1]标准。但由于它们都是以应用为目的的解释程序，通常都将效率与空间放在第一位，这就导致它们的程序结构比较复杂。本次毕业设计的目的是要了解Scheme解释程序的结构，以及对编程语言的本质的更深入的理解，因此就要避免复杂的设计。
本次毕业设计的主要参考为SICP[3]，解释程序的大部分设计模型都来自本书中（书中的解释程序是用Scheme本身写的）。该程序所涉及到的内容主要有词法分析、求值的环境模型、垃圾回收机制和虚拟的寄存器机器模型。
4 解释程序的整体结构 【买计算机毕业论文就到计算机毕业论文网】
整个解释器包含几大部分，首先是词法分析，将Scheme源程序代码表示为内部表示形式，即表结构；然后将表结构形式的源程序传到求值器中，以对表达式进行求值。在求值器对表达式求值的过程中，要基于虚拟的寄存器机器来做运算，所有的运算操作都是在寄存器中完成的。而寄存器机器又封装了对内存的组织与管理，并实现了垃圾回收机制来释放不会再被使用的Scheme对象。 [来源：http://think58.com]
解释器的整体结构图见图1。

图1 解释器的整体结构
4.1 词法分析器
词法分析是将源程序中的各种成分拆开，并解析成一个一个的基本元素，识别为原子或表，相应的创建每个基本元素对象，而该对象就含有元素的类型信息。再将这些对象组织成一张表结构的形式，形成代码的内部表示，以便在循环求值器中对其求值。
4.2 类型系统
在创建基本元素对应的对象时，该对象中要含有类型信息。类型系统就定义了Scheme语言中的9种数据类型，并将其嵌入到对象中。这样，在词法分析过程中只要创建相应类型的Scheme对象即可。该类型系统同时决定着Scheme源程序的内部表示的数据结构。
4.3 循环求值器
求值器对Scheme程序进行计算，它的计算方式要与Scheme程序的语义吻合。该求值器包含两个部分：
1、在求值一个组合式时，首先求值其中的子表达式，其中第一个子表达式的值就是运算符，而后将运算符子表达式的值作用于运算对象子表达式的值；
2、将一个复合过程应用于一级实际参数，就是在一个新的环境里求值这个过程的体。构造这一环境的方式就是用一个框架扩充该过程对象的环境部分，框架中包含的是这个过程的各个形式参数与这一过程应用的各个实际参数的约束，这就是求值的环境模型。 内容来自think58

[版权所有：http://think58.com]

上面两条规则描述了求值过程的基本循环，也就是它的核心部分。在这一循环中，表达式在环境中的求值被归约到过程对实际参数的应用，而这种应用又被归约到新的表达式在新的环境中的求值，如此下去，直到我们下降到符号（或称变量，其值可以在环境中找到）或基本内置过程（它们由解释程序实现）。这一求值循环体现为求值器里的两个关键操作“求值”和“应用”的相互作用，见图2。

图2 揭示计算机语言本质的求值－应用循环
4.4 虚拟的寄存器机器
在解释程序中，实现了一个虚拟的寄存器机器，就像真实的计算机一样，它也包含了一组寄存器、一块存储区域、以及一些类似汇编的基本操作。这一套基本操作扮演着机器的基本指令集的角色，它们执行的操作只是简单的从内存和寄存器中互相交换数据。Scheme代码的计算全都放在这部寄存器机器中进行。在寄存器机器中的Scheme代码是内部表结构形式，因此它们所操作的对象就是一张表，所执行的操作就是对这张表进行一些修改，由此来完成Scheme代码的计算。
4.5 内存管理与垃圾回收
Scheme程序的基本结构是表结构，为了使表结构适合创建和修改，把内存结构重新组织为基于向量的，因此所有的表操作，到最底层都归结为对向量形式的内存单元的操作。为封装这一细节，便创建了内存管理模块。

[来源：http://www.think58.com]

按Scheme标准规定来实现解释程序的话，就需要有无穷数量的存储器，而这是不可能的，因此就需要使用垃圾回收机制来维护一种无穷存储器的假象。考虑到Scheme本身的表结构，以及实现的复杂性，这里采用相对简单但却有优势的一种垃圾回收算法——停止并复制算法。其基本思想就是将存储器分成两半：“工作存储区”和“自由存储区”。当需要创建对象时，就从工作存储区中分配它们。当工作存储区满的时候就执行垃圾回收操作，将工作存储区中的有用对象复制到自由存储区中，并形成连续的位置。然后再交换两个存储区的角色，继续进行下去。在支持虚拟存储器的系统中，由于该算法是一种紧缩型垃圾回收算法，使得所有数据都被移到一片连续的存储位置中，因此可以避免很多换页操作。
5 解释程序的实现
5.1 类型系统
原子（atom）是Scheme的基本单位，它可以是基本数据、空表（null）和由原子或空表组成的表。Scheme中有9种互不相交数据类型，它们是布尔(boolean)、点对(pair)、符号(symbol)、数值(number)、字符(char)、字符串(string)、向量(vector)、端口(port) 和过程(procedure)类型。空表是一个隶属于其自身类型的特殊对象，它不能属于上述任何一种类型。互不相交是指一个对象能且只能属于其中一个类型。Scheme中对布尔值的规定是这样的，只有该对象是布尔类型并且值为假时才为假，否则总为真。这也就是说Scheme中的任何值都可以作为布尔值参与条件判断。在条件判断中，除了#f以外，所有值都被视为真。 think58.com
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<OT_LAMBDA>；相应的还有参数个数限制的模板类定义，偏特化版本为：template<> class Arity<OT_LAMBDA>；具体的操作执行过程就在这里实现。 copyright think58

[来源：http://think58.com]

5.2 词法分析
词法分析就是要将Scheme源程序中的原子都识别出来，并过滤掉空白和注释，将源程序组织为内部数据结构来表示。图4所示就是词法分析的主要流程图。
5.3 表达式求值的环境模型
表达式求值模型有两种：代换模型和环境模型。函数式程序设计中，可以采用代换模型。因为以同样的参数对同一过程的两次求值一定产生出同样的结果，可以认为过程是在计算数学函数。代换模型是具有漂亮的数学性质的简单模型。但由于Scheme并不是纯函数式编程语言，而且Scheme实现的是词法作用域，因此不能使用代换模型。在实现中采用环境模型作为求值模型。
5.3.1 环境模型
一个环境（environment）就是框架（frame）的一个序列，每个框架是包含着一些约束（binding）的表（可能为空），这些约束将一些变量名字关联于对应的值（在一个框架里，任何变量至多只能有一个约束）。每个框架还包含着一个指针，指向这一框架的外围环境（enclosing environment）。一个变量（variable）相对于某个特定环境的值（value），也就是在这一环境中，包含着该变量的第一个框架里这个变量的约束值。如果在序列中并不存在这一变量的约束，那么我们就说该变量在该特定环境中是无约束（unbound）的。如果在当前框架中找不到某个变量的约束，则应转到其外围环境中去查找。这样就实现了词法作用域。 本文来自think58 [资料来源：http://THINK58.com]

图4 词法分析流程图
环境对于求值过程是至关重要的，因为它确定了表达式求值的上下文。在解释程序开始运行后，会初始化一个全局环境，在这个环境中包含着一个框架，其中包含着所有关联于基本内置过程的绑定。只有在这个环境存在的情况下，一个表达式才有意义，如(+ 1 1)这样的表达式，其行为要取决于符号‘+’绑定到哪一个操作，在全局环境中它是与加法操作绑定起来的，但用户完全可以修改这个绑定，使它具有其它的意义。
[资料来源：www.THINK58.com]