-*- outline -*- 2007-03-18创建 * 改善 (2007-06-13)更正了垃圾回收后程序出错的错误，原因在于一些函数实现中操作 没有完全基于寄存器来做。以后在这方面还要检查几次。 完善了代码，加入了一个新操作，eof-object?。 改善了Huffman程序，可以直接运行./eval -s Huffman.scm来运行测试程序，并 且运行情况良好。 在优化编译下的结果，运行要快很多，现将第一个优化版本称为tos-alpha。 * 总结 (2007-04-30) 现已实现基本的Scheme特征，可以运行简单的Scheme程序，具体总结如下： ** 已实现的语法 lambda if quote define begin set! and or ** 已内置实现的标准过程 cons car cdr set-car! set-cdr! pair? + - * / = < > <= >= number? integer? number->string string->number eqv? eq? equal? not boolean? pair? null? list? symbol? symbol->string string->symbol char? char=? char<=? char>=? char->integer integer->char string? make-string string-length string-ref string-set! vector? make-vector vector-length vector-ref vector-set! procedure? apply (eval) ** 用于调试的过程 tos::register - 显示指定寄存器的内容 ** 已实现的类型系统 boolean char pair integer string symbol vector null procedure port未实现，另加入了语法性过程类型syntax，但它与基本过程是统一的。 ** 求值的环境模型 采用的环境是SICP中所述的环境模型，但稍有不同；其中环境表示为框架的表， 框架表示为约束的表，约束表示为变量与值的点对。 基本的环境操作有在当前框架中添加一个变量和值的约束；在整个环境中更改一 个变量的约束值；在指定框架中查找某个变量的约束；在整个环境中查找某个变 量的约束。 环境操作基于的基本操作有：cons car cdr set-car! set-cdr! ** 向量内存模型 将内存组织为向量的形式，整个可用内存分为两个向量，一个car的向量，一个 cdr的向量。相应的，指针表示为该向量的下标。 向量的基本操作为设置和获取某个位置的值。 ** 垃圾回收 采用了停止并拷贝的垃圾回收方式，因而需要两块可用内存，一个用作当前使用 内存，另一个用作后备内存。 与Scheme的表结构配合起来，垃圾回收算法相当简单，顺着表指针依次拷贝即可。 ** 寄存器机器模型 按照SICP所述的机器模型构建，但将栈也看作一个寄存器，即共有八个寄存器 （但现在看来应该多加入几个通用寄存器，用于中间寄存器，可简化寄存器操 作）。 寄存器机器提供的基本操作有：获取某个寄存器的内容（reg），设置某个寄存器 的内容（set），寄存器之间赋值的操作（assign），保存某寄存器到栈中 （save），从栈中恢复值到某寄存器（restore）。 ** 尾递归 按照SICP上的方式，对参数、表达式序列中的最后一个表达式作特殊处理，即恢 复以前保存的寄存器的值，不用再保存任何寄存器，然后对这最后一个表达式求 值即可。 * 发现一个缺陷（当天已解决） (2007-04-27) 当调用过程时发现错误而抛出异常后，栈可以简单的清空，但是其它寄存器的 值，尤其是将来肯定会用到的环境寄存器的值，却无法恢复。 一个很好的解决办法是，每一次入栈操作都向某个类提交信息，并设置相应的回 调函数，以便在异常发生时调用这些函数来恢复寄存器。而每一次出栈操作都将 这个信息取消。在异常发生时，可以在构造函数中查询这个类中的回调函数并调 用，以便系统复原。 * 求值部分整体改进 (2007-04-25) 完成了调用顺序的更改；将过程分为了语法性过程和基本内置过程；重写了部分 求值代码，使整体结构更清晰；加入了过程调用时对参数个数进行校验的功能； 新加入了一些新的基本操作和语法的实现，如：begin,pair?等等 现在的成果，已经将尾递归实现。但没有测试其效果。 * 更改过程调用的顺序（当天已成功） (2007-04-25) 原来采用的是SICP上面的顺序，即先求值操作符，再求值参数，再对操作符应用 参数。 但这样的话，每一个语法实现都要一个特例，不能与过程调用统一起来。而且也 无法实现参数个数的检查。 现在将用这样的顺序，即先求值操作符，准备好参数（不求值），立即对操作符 应用参数。在操作符的实现中，先检查参数个数是否与相应操作匹配。若是语法 性操作的话，就将参数作为代码序列来求值，最后一个结果就是其值；否则再对 参数求值。再若是基本操作，并将参数应用到操作符对应的运算；若是复合过程 的话，与参数进行绑定，同时检查参数个数是否匹配，再将参数应用到操作符。 这里每一个操作都要对应两个函数，一个用来检查参数和决定是否对参数求值， 另一个用来对参数进行实际的操作。 * 核心功能已实现 (2007-04-24) 按照R5RS，已经实现了以下功能。接下来应该向核心添加基本操作，并用Scheme 本身实现其它标准过程。 ** 基本表达式类型（4.1） 常量表达式；变量引用；过程调用；过程，包括三种参数形式；条件表达 式，两种形式；赋值。 ** 最高层定义（5.2.1） 只实现了(define variable exp)的形式。 ** 2007-04-24 新实现了car cdr set-car! set-cdr! +-*/等操作 * 垃圾回收有严重错误 (2007-04-18) 一旦进行垃圾回收后，就会丢失数据，使得输出错误。 原因：在解析器中的操作没有基于寄存器来做，因此导致了数据的丢失。 已经修正，垃圾回收本身也有一处错误。 * 前期工作小结 (2007-04-11) 总结前期完成的主要工作及质量，存在的问题和拟解决的方法 通过进一步的查看了解各方面的资料，尤其是SICP这本书，并且经过几次编程尝 试后，让我对解释器的类型系统有了一个比较全面而完整的认识。现在完成的类 型系统经初步测试，证明其工作良好。但最终是否有效，还有待后面的综合测试。 类型系统是整个Scheme解释器的基础，有了这一基础，就可以做内存管理、词法 分析等工作了。现在，内存管理（即垃圾回收功能）已经完成，并经过了初步测 试，可以达到预期目标。 此外，还初步实现了寄存器机器模型，以及一小部分基本操作。经过对以上完成 的系统的测试工作，也使我对解释器如何工作，有了一个初步的认识。 接下来应该做词法分析部分，完成这一块后，就可以进入程序的执行部分了。 现在存在的问题仍然是缺乏对程序执行原理的理解，更是因为如此，使得现在完 成的功能模块是否最终还能使用，也成了一个疑问。接下来只有通过对系统的进 一步实现，以及查看相关资料来逐步解决这一疑问。 在前面的工作中，我只完成了一小部分的文档。因为没有对系统全面的认识，所 以文档无法写得完整，而且由于急于要验证现在完成的部分是否可用，我便有意 的忽略了文档的编写工作。我计划一旦对系统有了全面的认识，并且构建起整体 结构后，会尽快补起相关的文档。 * TOS: Try On/Of Scheme 我的毕业设计课题为“Scheme解释器或编译器的设计与实现”。这是我的一次尝 试，也是对自己的一次挑战。希望我能完成它。 今天正式创建代码仓库，开始这一历程。 * 实现目标 采用UTF-8编码