函数式编程语言-Scheme解释程序的实现

摘  要
Scheme是一种函数式编程语言，是第一个完全支持词法作用域、第一级过程以及继续的LISP方言。它语法简洁但功能强大，而且非常优雅，具有数学的美感，同时蕴含着丰富的数学理论和程序设计技术。Scheme具有极高的开发效率，并且相当容易学习，它能使学习它的人从一开始就将注意力放到编程思想上，而不是停滞在学习繁琐的语法上。
在Scheme解释程序的设计中，充分采用了模块化的设计思想，首先将解释程序的整体结构与Scheme的核心内容理清，然后再设计解释程序的整体架构，并定义好各模块的结构和相关模块之间的接口，之后再逐模块地进行具体的代码实现工作。
整个解释器的核心是一个虚拟的寄存器机器，及其支持的一套基本指令集。该寄存器机器还要基于向量模型来管理内存，并实现垃圾回收机制。Scheme的源代码将被词法分析器解析成内部表结构来表示，再传入操作的解释模块中，转化为仅由基本指令组成的执行过程，在寄存器机器中执行。

关键词：解释程序；Scheme；垃圾回收；虚拟的寄存器机器

Implementation of the Scheme Interpreter
Abstract
Scheme, 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 interpreter's 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

课题背景
Scheme是一种函数式编程语言，是LISP的一种方言。它语法简洁但功能强大，Scheme的设计理念是：程序语言不是拿来“学”的，而是拿来“用”的。Scheme是非常优雅的，它具有数学的美感，蕴含着丰富的数学理论和程序设计技术。Scheme诞生后，由于其具有所有LISP的优点，而且简洁、强大、稳定、特别适合用于描述算法，以至于Scheme在教育界被广泛的使用，新一代优秀的计算机科学家中有很多人的“母语”就是Scheme。
我学习它可以更深入的体会程序设计的数学原理，对以前所学的知识进行一次融会贯通。实现一个解释程序，要有扎实的基础和编程能力，也要求对编程语言有更高层次的理解。选择它作为毕业设计，可以很好的考验我的基础知识和动手能力。

研究意义
模块化是成功的程序设计的关键。以提高生产力为目标的程序语言，必须良好地支持模块化程序设计。但是，新的作用域规则和分块编译的技巧是不够的——“模块化”不仅仅意味着把程序分成几个的“模块”，还需要能把它们有效的组合起来。我们分解程序的能力直接取决于将解决方案粘在一起的能力。为了协助模块化程序设计，程序语言必须提供优良的黏合剂。函数式程序语言提供了两种新的黏合剂——高阶函数与惰性求值，而Scheme就提供了这些。Scheme中的过程是一级对象，可以动态创建，可以存储于数据结构中，可以作为过程的结果返回，等等。研究Scheme，就可以从实践的角度来理解函数式编程，来体会模块化技术的极致，以及函数式编程带来的开发效率的提升。
Scheme是一门优雅的语言，并带有极高的开发效率，而且相当容易学习，它能使学习它的人从一开始就将注意力放到编程的思想上，而不会停滞在学习繁琐的语法上慢慢地耗尽耐心。作为国外大学计算机科学的一门必修课，我认为我们也应该把它作为学习计算机科学的起始点。这也是我的初衷。

研究方法
在设计中，充分采用模块化的设计思想，先将解释程序的整体结构与Scheme的核心内容理清，并设计好各模块的结构和相关模块之间的接口。之后，再逐步进行具体的实现。
整个解释器的核心是一个寄存器机器，以及其支持的一套基本指令集。通过扩展，将Scheme的源程序解释到这一套基本指令集上。这个寄存器机器还要管理内存，并实现垃圾回收机制。
Scheme的源代码将被词法分析器解析成内部表结构来表示，再传入操作的解释模块中，转化为仅由基本指令组成的执行过程，在寄存器机器中执行。








目  录
1 引言 1
1.1 课题背景 1
1.2 研究意义 1
1.3 研究方法 1
2 Scheme语言 2
2.1 发展历史与现状 2
2.2 Scheme语言介绍 2
2.3 Scheme的特点 3
3 相关理论基础 3
4 解释程序的整体结构 3
(毕业设计)
4.1 词法分析器 4
4.2 类型系统 4
4.3 循环求值器 4
4.4 虚拟的寄存器机器 5
4.5 内存管理与垃圾回收 5
5 解释程序的实现 6
5.1 类型系统 6
5.2 词法分析 7
5.3 表达式求值的环境模型 7
5.3.1 环境模型 7
5.3.2 环境操作 9
5.3.3过程应用的环境模型 9
5.3.4 环境模型的实现 10
5.4 尾递归 11
5.5 虚拟的寄存器机器 13
5.5.1 寄存器 14
5.5.2 存储模型 15
5.5.3 基本表操作的实现 16
5.5.4 停止并复制垃圾回收算法 17
5.5.5 虚拟的寄存器机器的实现 18
5.6 表达式求值过程 18
6 测试结果 19
6.1 测试尾递归 19
6.2 测试正确性与效率 20
结    论 21
参考文献 22
致    谢 23
声    明 24