本文介绍了如何使用 C# 实现一个简化 Scheme——iScheme 及其解释器。
如果你对下面的内容感兴趣：
- 实现基本的词法分析，语法分析并生成抽象语法树。
- 实现嵌套作用域和函数调用。
- 解释器的基本原理。
- 以及一些 C# 编程技巧。
那么请继续阅读。
如果你对以下内容感兴趣：
- 高级的词法/语法分析技术。
- 类型推导/分析。
- 目标代码优化。
本文则过于初级，你可以跳过本文，但欢迎指出本文的错误 :-)
代码样例
public static int Add(int a, int b) {
return a + b;
}
>> Add(3, 4)
>> 7
>> Add(5, 5)
>> 10
</div>
这段代码定义了 Add 函数，接下来的 >> 符号表示对 Add(3, 4) 进行求值，再下一行的 >> 7 表示上一行的求值结果，不同的求值用换行分开。可以把这里的 >> 理解成控制台提示符（即Terminal中的PS）。
什么是解释器
解释器（Interpreter）是一种程序，能够读入程序并直接输出结果，如上图。相对于编译器（Compiler），解释器并不会生成目标机器代码，而是直接运行源程序，简单来说：
解释器是运行程序的程序。
计算器就是一个典型的解释器，我们把数学公式（源程序）给它，它通过运行它内部的”解释器”给我们答案。
iScheme 编程语言
iScheme 是什么？
- Scheme 语言的一个极简子集。
- 虽然小，但变量，算术|比较|逻辑运算，列表，函数和递归这些编程语言元素一应俱全。
- 非常非常慢——可以说它只是为演示本文的概念而存在。
OK，那么 Scheme 是什么？
- 一种函数式程序设计语言。
- 一种 Lisp 方言。
- 麻省理工学院程序设计入门课程使用的语言（参见 MIT 6.001 和 计算机程序的构造与解释）。
使用 波兰表达式（Polish Notation）。
更多的介绍参见 [Scheme编程语言]。
以计算阶乘为例：
C#版阶乘
public static int Factorial(int n) {
if (n == 1) {
return 1;
} else {
return n * Factorial(n - 1);
}
}
</div>
iScheme版阶乘
(def factorial (lambda (n) (
if (= n 1)
1
(* n (factorial (- n 1))))))
</div>
数值类型
由于 iScheme 只是一个用于演示的语言，所以目前只提供对整数的支持。iScheme 使用 C# 的 Int64 类型作为其内部的数值表示方法。
定义变量
iScheme使用`def`关键字定义变量
>> (def a 3) >> 3 >> a >> 3</div>
算术|逻辑|比较操作
与常见的编程语言（C#, Java, C++, C）不同，Scheme 使用 波兰表达式，即前缀表示法。例如：
C#中的算术|逻辑|比较操作
// Arithmetic ops a + b * c a / (b + c + d) // Logical ops (cond1 && cond2) || cond3 // Comparing ops a == b 1 < a && a < 3</div>
对应的iScheme代码
; Arithmetic ops (+ a (* b c)) (/ a (+ b c d)) ; Logical ops (or (and cond1 cond2) cond3) ; Comparing ops (= a b) (< 1 a 3)</div>
需要注意的几点：
iScheme 中的操作符可以接受不止两个参数——这在一定程度上控制了括号的数量。
iScheme 逻辑操作使用 and , or 和 not 代替了常见的 && , || 和 ! ——这在一定程度上增强了程序的可读性。
顺序语句
iScheme使用 begin 关键字标识顺序语句，并以最后一条语句的值作为返回结果。以求两个数的平均值为例：
C#的顺序语句
int a = 3; int b = 5; int c = (a + b) / 2;</div>
iScheme的顺序语句
(def c (begin (def a 3) (def b 5) (/ (+ a b) 2)))</div>
控制流操作
iScheme 中的控制流操作只包含 if 。
if语句示例
>> (define a (if (> 3 2) 1 2)) >> 1 >> a >> 1</div>
列表类型
iScheme 使用 list 关键字定义列表，并提供 first 关键字获取列表的第一个元素；提供 rest 关键字获取列表除第一个元素外的元素。
iScheme的列表示例
>> (define alist (list 1 2 3 4)) >> (list 1 2 3 4) >> (first alist) >> 1 >> (rest alist) >> (2 3 4)</div>
定义函数
iScheme 使用 func 关键字定义函数：
iScheme的函数定义
(def square (func (x) (* x x))) (def sum_square (func (a b) (+ (square a) (square b))))</div>
对应的C#代码
public static int Square (int x) {
return x * x;
}
public static int SumSquare(int a, int b) {
return Square(a) + Square(b);
}
</div>
递归
由于 iScheme 中没有 for 或 while 这种命令式语言（Imperative Programming Language）的循环结构，递归成了重复操作的唯一选择。
以计算最大公约数为例：
iScheme计算最大公约数
(def gcd (func (a b)
(if (= b 0)
a
(func (b (% a b))))))
</div>
对应的C#代码
public static int GCD (int a, int b) {
if (b == 0) {
return a;
} else {
return GCD(b, a % b);
}
}
</div>
高阶函数
和 Scheme 一样，函数在 iScheme 中是头等对象，这意味着：
- 可以定义一个变量为函数。
- 函数可以接受一个函数作为参数。
- 函数返回一个函数。
iScheme 的高阶函数示例
; Defines a multiply function.
(def mul (func (a b) (* a b)))
; Defines a list map function.
(def map (func (f alist)
(if (empty? alist)
(list )
(append (list (f (first alist))) (map f (rest alist)))
)))
; Doubles a list using map and mul.
>> (map (mul 2) (list 1 2 3))
>> (list 2 4 6)
</div>
小结
对 iScheme 的介绍就到这里——事实上这就是 iScheme 的所有元素，会不会太简单了？ -_-
接下来进入正题——从头开始构造 iScheme 的解释程序。
解释器构造
iScheme 解释器主要分为两部分，解析（Parse）和求值（Evaluation）：
1、解析（Parse）：解析源程序，并生成解释器可以理解的中间（Intermediate）结构。这部分包含词法分析，语法分析，语义分析，生成语法树。
2、求值（Evaluation）：执行解析阶段得到的中介结构然后得到运行结果。这部分包含作用域，类型系统设计和语法树遍历。
词法分析
词法分析负责把源程序解析成一个个词法单元（Lex），以便之后的处理。
iScheme 的词法分析极其简单——由于 iScheme 的词法元素只包含括号，空白，数字和变量名，因此C#自带的 String#Split 就足够。
iScheme的词法分析及测试
pu