Report of Scheme Interpreter in Python

---

这是一个Scheme语言的一个小型解释器，使用Python2.7编写。
您可以在任意一台安装了Python2的机器上获得所有代码并运行。
在终端中输入schpy.py [file]来执行这个解释器。若输入文件名，将先执行文件再进入交互模式，否则直接进入交互模式。
这是一个脆弱的解释器，希望使用它的人能善待它。

---

学习的内容

1.Scheme的基本操作

通过阅读SICP[1]，可以获得以下知识：

• 前缀表达式

• lambda匿名函数

• 应用序与正则序

• 统一数据结构list

2.实现一个解释器的基本步骤

1 读入字符流进行处理

2 分词

3 read-eval-print-loop (REPL)

3.Markdown语法

这是一个使用Markdown编写的文档。

---

实现解释器

1.tokenizer

利用python自带的string操作，把括号分开。
如果一个字符串里面存着空格，先用一个另外的字符串代替。
然后通过python的split操作分开个个元素。
再通过替换把token转化成正确的格式。
此时特殊语法'也会被转化成正确的语法。

2.parse

递归进行分词。同一级别的token放在同一个list中

3.eval过程

手动判断各种特殊语法结构，对于复合过程执行apply过程，否则根据特殊过程执行相应的函数

4.apply过程

计算参数绑定到环境里面，如果遇到底层函数如加减乘除执行底层过程，否则执行eval过程

---

遇到的问题

• 对于apply函数，对一个底层操作符执行判断出现了问题，容易导致识别操作符失败。而apply一个组合过程则不会出现这样的问题
  解决方法：在apply过程中对底层操作符进行特判

• 对于基本元素的表示略为混乱。之前一直无法通过测试返回RE的原因是对于symbol，有时候处理会进行转义，有时候不会，导致匹配时出现问题。
  解决方法：统一表示。输出symbol时再转义

• python内置数据结构与scheme数据结构的不统一，导致运算混乱。
  解决方法：表示时统一使用scheme数据结构的表示方法，最后求值转化成python数据结构求值。

• 执行N皇后这样的程序，会因为递归深度过大而抛出异常。
  解决方法：python语言特性，无法解决

• 对大整数，无法转成浮点数运算。
  解决方法：python语言特性，无法解决

• 未实现的功能：部分底层函数和语法结构，宏，惰性求值等等

---

思考与感想

• 最早的时候参考了网上的资料[2]，同时也看了一些文章，里面基本介绍的都是如何实现interpreter以运行scheme的一个子集。实际上最有用的是SICP的第三章和第四章，尽管是Bootstrap，但是详细阐述了如何写一个解释器，并介绍了环境模型。我的解释器框架是按照上面说的实现，底层则自行填充。

• 环境模型是整个解释器的核心。一开始函数执行不对便是因为环境模型实现不正确。理解了环境模型，实现一个简单的不处理副作用的解释器便容易很多。

• 最早接触的函数式编程语言是haskell，这是一个无副作用的纯函数式编程语言。这次接触了scheme，总的感觉不如Haskell优美。事实上，由于最早入门语言是basic，后来接触了Pascal和C++，个人更习惯于命令式编程的思考模式。用python实现scheme interpreter，便是考虑到了命令式编程的习惯和支持函数式编程语法的便利。

• 使用python实现scheme interpreter，相当于对scheme解释了2遍，导致运算效率低下。而且由于第一次写这种项目，整个构思不够精细，实现过程中出现不少问题。此scheme interpreter也仅仅是一个真正interpreter的subset，若有不对之处，敬请见谅。

---

作者：@Juda