hepengfei / tos Goto Github PK

-*- 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编码