Scheme解释程序的实现

包括论文,设计,论文字数:13528,页数:29

摘  要
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

目  录

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