s sllt
← All posts
· 23 min read ·
#scheme #python #interpreter

如何写一个Scheme解释器

目录 · Table of Contents

本文假设你会使用 Python。

我们会分两步来构建这个解释器：

  1. 先实现一个 Scheme 语法式的简单计算器：只支持加、减、乘、除，但麻雀虽小五脏俱全——借它跑通解释器最核心的四个环节：表达式树（Pair）、语法解析（Read）、递归求值（Eval）与交互循环（REPL）；
  2. 再逐步把计算器升级为完整的 Scheme 解释器：在计算器的骨架上依次加入 环境与变量（define）、特殊形式（quote、if、cond、let 等） 以及 自定义函数与闭包（lambda）。

关于 Scheme 语言本身的更多背景，可以参考维基百科的 Scheme 词条。完整代码可以在文末查看，也可以直接下载 scheme.py。

1. Scheme 语法式的计算器

1.1 计算器的语法与求值规则

我们先从最简单的前缀表达式计算器开始。这个简化版计算器只包含加（+）、减（-）、乘（*）、除（/）四种运算。

在 Scheme 中，所有的运算都写成 (操作符 参数1 参数2 ...) 的前缀形式。加法和乘法可以接收任意数量的参数：

scheme
1scm> (+ 1 2 3 4)
210
3scm> (+)
40
5scm> (* 1 2 3 4)
624
7scm> (*)
81

减法（-）有两种情况：只传入 1 个参数时，求这个数的相反数；传入 2 个及以上参数时，用第一个数依次减去后面的数，例如 (- 10 1 2 3) 等同于 10 - 1 - 2 - 3。除法（/）也是类似的规则（单参数求倒数，多参数依次相除）：

scheme
1scm> (- 10 1 2 3)
24
3scm> (- 3)
4-3
5scm> (/ 15 12)
61.25
7scm> (/ 30 5 2)
83.0
9scm> (/ 10)
100.1

表达式可以任意多层地嵌套。当计算一个嵌套表达式时，求值器会先递归求出所有内层子表达式的值，再把结果传给外层操作符：

scheme
1scm> (- 100 (* 7 (+ 8 (/ -12 -3))))
216.0

上面这个表达式的求值过程就像剥洋葱一样，从最内层向外层逐步归约：

text
1(/ -12 -3) => 4.0
2(+ 8 4.0) => 12.0
3(* 7 12.0) => 84.0
4(- 100 84.0) => 16.0

接下来我们就用 Python 编写这个计算器。整体流程非常清晰：

text
1读取源码字符串 -> 切分 Token -> 解析为 Pair 表达式树 -> 递归遍历求值 -> 打印结果

1.2 表达式树：Pair 与 nil

观察上面的 Scheme 表达式会发现：每一个括号表达式本质上都是一个列表，列表的第一个元素是操作符（函数名），后面的元素是传给它的参数；如果某个参数本身又是括号表达式，那它就是一个嵌套的子列表。

在 Lisp/Scheme 家族中，列表是由 点对（Pair） 和 空表（nil） 串起来的单向链表：

  • 每个 Pair(first, second) 节点包含两部分：first（即 car，存放当前元素）和 second（即 cdr，指向剩余链表）；
  • 链表的末尾以单例对象 nil（即空表 ()）结束。

为什么不直接用 Python 内置的 list，而要专门写一个 Pair 类呢？因为后面进入完整的 Scheme 解释器时，Scheme 语言内置的数据结构本身就是 Pair 和 nil（包括 (1 . 2) 这样的非正规点对）。现在用 Pair 来表示语法树，后面实现 Scheme 的 quote、cons、car、cdr 时就会发现：语法树本身就是 Scheme 的列表数据（代码即数据，同像性），连一行多余的转换代码都不用写。

下面是 Pair 与 nil 的核心实现：

python
1class _Nil:
2 """表示 Scheme 中的空表 ()"""
3 def __repr__(self):
4 return "nil"
5
6 def __str__(self):
7 return "()"
8
9 def __len__(self):
10 return 0
11
12 def __iter__(self):
13 return iter(())
14
15 def map(self, fn):
16 return self
17
18
19nil = _Nil()
20
21
22class Pair:
23 """表示链表节点 (first, second)"""
24 def __init__(self, first, second=nil):
25 self.first = first
26 self.second = second
27
28 def __repr__(self):
29 return f"Pair({self.first!r}, {self.second!r})"
30
31 def __str__(self):
32 return to_scheme(self)
33
34 def __len__(self):
35 count, current = 0, self
36 while isinstance(current, Pair):
37 count += 1
38 current = current.second
39 return count
40
41 def __iter__(self):
42 current = self
43 while isinstance(current, Pair):
44 yield current.first
45 current = current.second
46
47 def __getitem__(self, index):
48 for i, item in enumerate(self):
49 if i == index:
50 return item
51 raise IndexError("Pair index out of range")
52
53 def map(self, fn):
54 return Pair(fn(self.first), self.second.map(fn))

来看看 Pair 的使用方式。由 1 和 2 组成的列表 (1 2) 表示为：

python
1>>> s = Pair(1, Pair(2, nil))
2>>> s
3Pair(1, Pair(2, nil))
4>>> print(s)
5(1 2)

因为我们实现了 __len__、__getitem__ 和 map，可以非常方便地操作这个链表：

python
1>>> len(s)
22
3>>> s[1]
42
5>>> print(s.map(lambda x: x + 4))
6(5 6)

而像 (+ (* 3 4) 5) 这样的嵌套算术表达式，用 Pair 构造出来就是一棵表达式树：

python
1>>> expr = Pair('+', Pair(Pair('*', Pair(3, Pair(4, nil))), Pair(5, nil)))
2>>> print(expr)
3(+ (* 3 4) 5)
4>>> expr.second.first.second.first
53

1.3 解析表达式（词法分析与语法分析）

手写 Pair('+', Pair(Pair('*', ...))) 显然太繁琐了。解析器（Reader）的任务，就是把用户输入的字符串 '(+ 1 (* 2.3 45))' 自动转换成上面的 Pair 树。这个过程分为两步：词法分析（Tokenize） 和 语法分析（Read）。

第一步：词法分析 tokenize

词法分析负责把源码字符串拆成一个个最小的语法单元（token）。

  • 空白字符用来分隔 token，本身直接跳过；
  • 分号 ; 到行尾是注释，直接跳过；
  • 左右括号 (、) 和单引号 ' 各自单独作为一个 token；
  • 其余连续字符（如 +、2.3、define）合并为一个 token。
python
1>>> tokenize('(+ 1 (* 2.3 45))')
2['(', '+', '1', '(', '*', '2.3', '45', ')', ')']

同时，我们用一个 atom(token) 函数把单个 token 转换成对应的原子值：能转成整数或浮点数的就转成 int / float，#t 和 #f 转成布尔值，其余标识符保持为字符串（作为符号）：

python
1def atom(token):
2 if token == "#t":
3 return True
4 if token == "#f":
5 return False
6 try:
7 return int(token)
8 except ValueError:
9 try:
10 return float(token)
11 except ValueError:
12 return token

第二步：递归下降语法分析 scheme_read

拿到 token 流之后，我们用一个带指针的 Buffer 对象按顺序消费 token，并用两个互相递归的函数 scheme_read 和 read_tail 把平铺的 token 还原成嵌套的 Pair 树：

  • scheme_read(src) 读取一个完整的表达式：
    • 如果取出的 token 是 '('，说明遇到了列表开头，调用 read_tail(src) 读取列表剩余部分；
    • 如果是普通原子 token，直接调用 atom(token) 返回。
  • read_tail(src) 读取括号列表的剩余部分：
    • 如果当前看到的是 ')'，消费掉它并返回 nil（列表结束）；
    • 否则，先调用 scheme_read(src) 读出列表的第一个元素（它本身可能又是一个子列表！），再递归调用 read_tail(src) 读出剩余链表，最后用 Pair(first, rest) 拼起来。
python
1def scheme_read(src):
2 if not src.more:
3 raise IncompleteInput("unexpected end of input")
4 token = src.pop_first()
5 if token == "(":
6 return read_tail(src)
7 if token == "'":
8 return Pair("quote", Pair(scheme_read(src), nil))
9 if token in (")", "."):
10 raise SchemeSyntaxError(f"unexpected token: {token}")
11 return atom(token)
12
13
14def read_tail(src):
15 if not src.more:
16 raise IncompleteInput("unexpected end of input while reading list")
17 if src.current() == ")":
18 src.pop_first()
19 return nil
20 first = scheme_read(src)
21 rest = read_tail(src)
22 return Pair(first, rest)

测试一下解析效果：

python
1>>> expression = scheme_read(Buffer(tokenize('(+ 1 (* 2.3 45))')))
2>>> expression
3Pair('+', Pair(1, Pair(Pair('*', Pair(2.3, Pair(45, nil))), nil)))
4>>> print(expression)
5(+ 1 (* 2.3 45))

仅仅二十几行代码，任意多层嵌套的括号表达式就已经变成规整的 Pair 树了。

1.4 计算器的求值与 REPL

有了 Pair 表达式树，怎么算出它的结果呢？

整个求值器由两个相互配合的函数组成：calc_eval（求值表达式） 和 calc_apply（执行操作符）。

calc_eval(exp) 的逻辑只有两种情况：

  1. 如果 exp 是数字（int 或 float），它就是自求值的，直接返回它自己；
  2. 如果 exp 是 Pair 列表，说明是一次运算调用：先用 exp.second.map(calc_eval) 递归地把所有参数子表达式求值，然后把操作符 exp.first 和求好值的参数列表传给 calc_apply。
python
1def calc_eval(exp):
2 """Evaluate a Calculator expression."""
3 if isinstance(exp, (int, float)):
4 return exp
5 elif isinstance(exp, Pair):
6 arguments = exp.second.map(calc_eval)
7 return calc_apply(exp.first, arguments)
8 else:
9 raise TypeError(f"{exp} is not a number or call expression")

而 calc_apply(operator, args) 则纯粹负责根据操作符的名字，对已经算出来的数字列表执行加减乘除：

python
1def calc_apply(op, args):
2 """Apply the named operator to a list of args."""
3 if not isinstance(op, str):
4 raise TypeError(f"{op} is not a symbol")
5 if op == "+":
6 return sum(args)
7 elif op == "-":
8 if len(args) == 0:
9 raise TypeError("- requires at least 1 argument")
10 elif len(args) == 1:
11 return -args.first
12 else:
13 return reduce(operator.sub, args.second, args.first)
14 elif op == "*":
15 return reduce(operator.mul, args, 1)
16 elif op == "/":
17 if len(args) == 0:
18 raise TypeError("/ requires at least 1 argument")
19 elif len(args) == 1:
20 return 1 / args.first
21 else:
22 return reduce(operator.truediv, args.second, args.first)
23 else:
24 raise TypeError(f"{op} is an unknown operator")

我们来单独测试 calc_apply 和 calc_eval：

python
1>>> calc_apply('+', as_scheme_list(1, 2, 3))
26
3>>> calc_apply('-', as_scheme_list(10, 1, 2, 3))
44
5>>> calc_apply('*', nil)
61
7>>> calc_apply('/', as_scheme_list(40, 5))
88.0
9>>> print(expr)
10(+ (* 3 4) 5)
11>>> calc_eval(expr)
1217

最后，把读取（scheme_read）、求值（calc_eval）和打印（print）放进一个 while True 循环，并加上异常捕获，就得到了一个交互式的 REPL（Read-Eval-Print Loop）：

python
1def read_eval_print_loop():
2 """Run a read-eval-print loop for calculator."""
3 while True:
4 try:
5 line = input("calc> ")
6 src = Buffer(tokenize(line))
7 while src.more:
8 expression = scheme_read(src)
9 print(calc_eval(expression))
10 except (SchemeError, TypeError, ValueError, ZeroDivisionError) as err:
11 print(f"{type(err).__name__}: {err}")
12 except (KeyboardInterrupt, EOFError):
13 print("Calculation completed.")
14 return

运行效果如下：

scheme
1calc> (* 1 2 3)
26
3calc> (+)
40
5calc> (+ 2 (/ 4 8))
62.5
7calc> (+ 2 2) (* 3 3)
84
99
10calc> (/ 1 0)
11ZeroDivisionError: division by zero

到这里，第一阶段的计算器就完成了！回顾一下，我们只写了不到 150 行代码，就已经打通了 Pair 语法树、scheme_read 递归下降解析、calc_eval / calc_apply 求值循环。

2. 从计算器升级到 Scheme 解释器

上面的计算器只能计算写死的 +、-、*、/。要将它变成一个真正的 Scheme 解释器，我们需要在它的骨架上补齐三块拼图：

  1. 环境与变量（Environment）：让求值器能够记住变量（例如 (define pi 3.14)），并把内置函数也统一存放在环境中；
  2. 特殊形式（Special Forms）：支持 quote、if、define、cond、let 等不遵循“先计算所有参数”规则的语法；
  3. 函数与闭包（Procedures & Closures）：支持用 lambda 创建自定义函数，并实现词法作用域（Lexical Scoping）。

2.1 环境与变量查找（Env）

在计算器里，操作符 +、- 是用 if op == '+' 硬编码在 calc_apply 里的；而在真正的 Scheme 中，+、*、car、cons 和用户自己用 define 定义的变量没有任何区别——它们都是绑定在 环境（Environment） 中的名字。

为了支持函数调用时的局部作用域，环境不能只是一个全局字典，而应该是一条由多个 环境帧（Frame） 串起来的链表：

  • 每个 Env 本身继承自 Python 的 dict，保存当前作用域的变量名和值；
  • 同时它持有一个指向外层环境的指针 self.outer（全局环境的 outer 为 None）；
  • 当查找一个变量 name 时，先看当前字典里有没有；如果没有，就顺着 self.outer 一直往外层找；直到最外层还找不到，就抛出未绑定符号错误。
python
1class Env(dict):
2 """一个词法作用域环境帧，通过 outer 指向外层环境"""
3 def __init__(self, params=(), args=(), outer=None):
4 params_list = list(params)
5 args_list = list(args)
6 if len(params_list) != len(args_list):
7 raise SchemeError(
8 f"expected {len(params_list)} arguments, got {len(args_list)}"
9 )
10 super().__init__(zip(params_list, args_list))
11 self.outer = outer
12
13 def find(self, name):
14 """返回绑定了 name 的最内层环境帧"""
15 if name in self:
16 return self
17 if self.outer is not None:
18 return self.outer.find(name)
19 raise SchemeError(f"unbound symbol: {name}")

有了 Env，我们就可以初始化一个包含常用内置过程的标准全局环境 standard_env()。 特别值得注意的是列表操作：因为我们的语法树原本就是用 Pair 和 nil 构造的，所以在全局环境里注册 Scheme 列表函数几乎不需要额外代码——cons 就是 Pair 本身，car 就是取 .first，cdr 就是取 .second：

python
1def standard_env():
2 env = Env()
3 env.update({
4 "+": calc_add,
5 "-": calc_sub,
6 "*": calc_mul,
7 "/": calc_div,
8 "=": lambda *xs: compare("=", operator.eq, *xs),
9 "<": lambda *xs: compare("<", operator.lt, *xs),
10 ">": lambda *xs: compare(">", operator.gt, *xs),
11 "cons": Pair,
12 "car": lambda p: p.first,
13 "cdr": lambda p: p.second,
14 "list": as_scheme_list,
15 "null?": lambda x: x is nil,
16 "pair?": lambda x: isinstance(x, Pair),
17 "pi": math.pi,
18 # ... 其他内置函数
19 })
20 return env

2.2 升级求值器与特殊形式（scheme_eval）

现在我们把 calc_eval(exp) 升级为接收环境参数的 scheme_eval(expr, env)。

当 scheme_eval 收到一个表达式 expr 时，它会按以下顺序分派：

  1. 符号（Symbol）：比如 pi、x 或 +，直接去环境中查找 env.find(expr)[expr]；
  2. 自求值原子（数字、布尔值 #t/#f、字符串）：直接返回本身；
  3. 特殊形式（Special Forms）：如果 expr 是 Pair 列表，且第一个元素是 quote、if、define、set!、lambda、begin、let、and、or、cond 之一，则按各自的专门规则求值；
  4. 普通函数调用：如果以上都不是，说明是普通的过程调用（如 (+ 1 2) 或 (square 5)）——先用 scheme_eval 算出第一个位置的函数对象，再对后面所有参数求值，最后交给 scheme_apply 调用！

为什么第 3 步的“特殊形式”不能直接走第 4 步的普通函数调用呢？来看看几个典型例子：

quote（引用）

在普通调用中，(f a b) 会把 a 和 b 当作变量去求值。但有时候我们就是想把 (1 2 3) 或符号 hello 当作原始数据，不想让求值器去算它。quote 的作用就是原封不动地返回未求值的参数本身：

python
1if form == "quote":
2 check_form(expr, 2, 2)
3 return rest.first

而在解析器 scheme_read 中，我们已经把单引号语法糖 'expr 自动转换成了 Pair("quote", Pair(expr, nil))。因此：

scheme
1scm> (quote (+ 1 2))
2(+ 1 2)
3scm> '(1 2 3)
4(1 2 3)

if（条件分支）

如果 if 是普通函数，那么执行 (if #t 42 (/ 1 0)) 时，求值器会先把三个参数全部算出来，立刻触发 / 1 0 除零异常！ 作为特殊形式，if 必须先只计算条件表达式，根据结果是真是假（Scheme 中只有 #f 为假，0 和 () 都是真），只对被选中的那个分支求值：

python
1if form == "if":
2 check_form(expr, 3, 4)
3 if is_true(scheme_eval(rest.first, env)):
4 return scheme_eval(rest.second.first, env)
5 if len(expr) == 4:
6 return scheme_eval(rest.second.second.first, env)
7 return UNSPECIFIED

define 与 set!（变量绑定与修改）

(define x (+ 1 2)) 不能先对 x 求值（因为 x 还没定义！）。它需要保持第一个参数 target 不求值，只对第二个参数 (+ 1 2) 求值，然后存入当前环境 env[target]：

python
1if form == "define":
2 check_form(expr, 3)
3 target = rest.first
4 if is_symbol(target):
5 check_form(expr, 3, 3)
6 env[target] = scheme_eval(rest.second.first, env)
7 return UNSPECIFIED
8 # 函数定义简写：(define (square x) (* x x))，见下一节
9 ...
10
11if form == "set!":
12 check_form(expr, 3, 3)
13 target = rest.first
14 require(is_symbol(target), "set! target must be a symbol")
15 env.find(target)[target] = scheme_eval(rest.second.first, env)
16 return UNSPECIFIED

注意 define 和 set! 的区别：define 直接在当前环境帧 env 中新建或覆盖绑定；而 set! 会通过 env.find(target) 找到变量所在的外层环境帧并修改它。

2.3 自定义函数、闭包与词法作用域（lambda 与 Procedure）

现在来到了整个解释器最精彩的部分：如何实现 lambda 匿名函数与闭包？

看下面这段经典的 Scheme 代码：

scheme
1(define make-adder
2 (lambda (n)
3 (lambda (x) (+ x n))))
4
5(define add10 (make-adder 10))
6(add10 32) ; => 42

当 make-adder 调用结束返回内层的 (lambda (x) (+ x n)) 时，为什么 add10 依然记得当时的参数 n 是 10？

答案很简单：一个函数在被定义（执行 lambda）的那一刻，不仅要记住自己的形参列表 params 和函数体 body，还要把定义它时的环境 env 一起打包保存下来！ 这个“函数代码 + 定义时的环境”的组合体，就叫做闭包（Closure）。

在 Python 中，我们用一个 Procedure 类来表示用户定义的 Scheme 函数：

python
1@dataclass
2class Procedure:
3 """用户定义的 Scheme 过程（闭包）"""
4 params: list[Symbol]
5 body: Pair
6 env: Env
7
8 def __call__(self, *args):
9 # 调用时：以定义时的环境 self.env 为外层环境，创建新的局部环境帧
10 local_env = Env(self.params, args, self.env)
11 return eval_all(self.body, local_env)

仔细看 Procedure.__call__ 的那两行代码：

  1. 当 (make-adder 10) 被调用时，解释器创建了一个局部环境 E1（其中 n = 10，E1.outer 指向全局环境）；
  2. 在 E1 中求值内层的 (lambda (x) (+ x n)) 时，生成的 Procedure 对象把 self.env = E1 保存了进去，这就是 add10；
  3. 随后执行 (add10 32) 时，add10.__call__(32) 创建了一个新的局部环境 E2（其中 x = 32），并且令 E2.outer = self.env（即 E1）！
  4. 在 E2 中计算 (+ x n) 时：
    • 查 x：在 E2 中直接找到 32；
    • 查 n：E2 中没有，顺着 E2.outer 找到 E1 中的 10；
    • 查 +：E2 和 E1 中都没有，顺着 E1.outer 在全局环境中找到加法函数 calc_add！

理解了 Procedure，scheme_eval 中处理 lambda、函数简写 (define (f x) ...) 以及普通函数调用的代码就极其直观了：

python
1if form == "lambda":
2 check_form(expr, 3)
3 params = check_params(rest.first)
4 return Procedure(params, rest.second, env)

而在 define 中，如果发现第一个参数 target 不是符号而是一个列表（例如 (define (square x) (* x x))），它其实就是 (define square (lambda (x) (* x x))) 的语法糖，直接构造一个 Procedure 绑定到函数名上即可：

python
1if isinstance(target, Pair) and is_symbol(target.first):
2 name = target.first
3 params = check_params(target.second)
4 env[name] = Procedure(params, rest.second, env)
5 return UNSPECIFIED

至于 scheme_eval 最后的普通函数调用，因为 Procedure 实现了 __call__ 方法，它和 Python 内置函数一样都是 callable 的，所以 scheme_apply 甚至不需要区分内置函数和用户自定义的 Procedure：

python
1# 普通函数调用：先求值操作符，再求值所有实参，最后应用
2operator_proc = scheme_eval(first, env)
3operands = rest.map(lambda sub_expr: scheme_eval(sub_expr, env))
4return scheme_apply(operator_proc, operands)

2.4 其他常用特殊形式（begin、let、and、or、cond）

有了上面的基础，剩下的几个常用特殊形式只需几行代码就能全部拿下：

  • begin：按顺序依次求值一系列表达式，返回最后一个表达式的值（直接调用 eval_all(rest, env)）；
  • let：创建局部绑定，例如 (let ((x 6) (y 7)) (* x y))。在当前环境 env 下先算出每个绑定右侧的值，然后构造一个新的子环境 Env(names, values, env) 求值主体；
  • and 与 or：从左到右依次求值，遇到假值（and）或真值（or）立即短路返回；
  • cond：多路条件分支，依次检查每个子句的条件，执行第一个条件为真的子句（或最后的 else 子句）。

3. 完整代码与运行示例

在最终的 REPL 中，我们再做一个实用的小改进：当用户输入多行代码（比如跨行的 define 函数定义，括号还没闭合）时，parse_program 会抛出 IncompleteInput 异常。REPL 捕获到这个异常后不报错，而是把提示符从 scm> 切换成 ... ，继续等待用户输入下一行，直到括号完全闭合后再统一执行。

下面是完整的 scheme.py（需要 Python 3.10+），也可以直接下载源码：

展开完整 scheme.py
python
1#!/usr/bin/env python3
2"""A self-contained Scheme interpreter in Python, built around Pair and nil."""
3
4from __future__ import annotations
5
6import json
7import math
8import operator
9import sys
10from dataclasses import dataclass
11from functools import reduce
12from pathlib import Path
13from typing import Any, Callable, Iterable, Iterator
14
15
16# 1. Errors & Basic Types ------------------------------------------------
17
18
19class SchemeError(Exception):
20 """Base exception for Scheme evaluation and syntax errors."""
21
22
23class SchemeSyntaxError(SchemeError):
24 pass
25
26
27class IncompleteInput(SchemeSyntaxError):
28 pass
29
30
31class String(str):
32 """A Scheme string literal (distinct from a Scheme symbol, which is a plain str)."""
33
34 def __repr__(self) -> str:
35 return json.dumps(str(self), ensure_ascii=False)
36
37
38Symbol = str
39
40
41class _Unspecified:
42 def __repr__(self) -> str:
43 return "UNSPECIFIED"
44
45
46UNSPECIFIED = _Unspecified()
47
48
49# 2. Pair and nil (S-Expression Linked Lists) ----------------------------
50
51
52class _Nil:
53 """The empty list () in Scheme."""
54
55 def __repr__(self) -> str:
56 return "nil"
57
58 def __str__(self) -> str:
59 return "()"
60
61 def __len__(self) -> int:
62 return 0
63
64 def __iter__(self) -> Iterator[Any]:
65 return iter(())
66
67 def __bool__(self) -> bool:
68 return False
69
70 def map(self, fn: Callable[[Any], Any]) -> _Nil:
71 return self
72
73
74nil = _Nil()
75
76
77class Pair:
78 """A cons cell (first, second) representing Scheme pairs and lists."""
79
80 def __init__(self, first: Any, second: Any = nil) -> None:
81 self.first = first
82 self.second = second
83
84 def __repr__(self) -> str:
85 return f"Pair({self.first!r}, {self.second!r})"
86
87 def __str__(self) -> str:
88 return to_scheme(self)
89
90 def __len__(self) -> int:
91 count = 0
92 current: Any = self
93 while isinstance(current, Pair):
94 count += 1
95 current = current.second
96 if current is not nil:
97 raise SchemeError("length requires a proper list")
98 return count
99
100 def __iter__(self) -> Iterator[Any]:
101 current: Any = self
102 while isinstance(current, Pair):
103 yield current.first
104 current = current.second
105 if current is not nil:
106 raise SchemeError("expected a proper list, got dotted pair")
107
108 def __getitem__(self, index: int) -> Any:
109 if index < 0:
110 raise IndexError("negative index not supported")
111 for i, item in enumerate(self):
112 if i == index:
113 return item
114 raise IndexError("Pair index out of range")
115
116 def __eq__(self, other: object) -> bool:
117 return (
118 isinstance(other, Pair)
119 and self.first == other.first
120 and self.second == other.second
121 )
122
123 def map(self, fn: Callable[[Any], Any]) -> Pair:
124 if not isinstance(self.second, (Pair, _Nil)):
125 raise SchemeError("map requires a proper list")
126 return Pair(fn(self.first), self.second.map(fn))
127
128
129def as_scheme_list(*items: Any) -> Pair | _Nil:
130 """Convert a sequence of Python values into a Scheme linked list."""
131 result: Pair | _Nil = nil
132 for item in reversed(items):
133 result = Pair(item, result)
134 return result
135
136
137def is_symbol(value: Any) -> bool:
138 return isinstance(value, str) and not isinstance(value, String)
139
140
141def is_proper_list(value: Any) -> bool:
142 while isinstance(value, Pair):
143 value = value.second
144 return value is nil
145
146
147def to_scheme(value: Any) -> str:
148 """Format a runtime value using standard Scheme notation."""
149 if value is True:
150 return "#t"
151 if value is False:
152 return "#f"
153 if value is nil:
154 return "()"
155 if value is UNSPECIFIED:
156 return ""
157 if isinstance(value, String):
158 return json.dumps(str(value), ensure_ascii=False)
159 if isinstance(value, str):
160 return value
161 if isinstance(value, Pair):
162 parts: list[str] = []
163 current: Any = value
164 while isinstance(current, Pair):
165 parts.append(to_scheme(current.first))
166 current = current.second
167 if current is not nil:
168 parts.append(".")
169 parts.append(to_scheme(current))
170 return "(" + " ".join(parts) + ")"
171 if isinstance(value, Procedure):
172 return "<procedure>"
173 if callable(value):
174 return "<builtin-procedure>"
175 return str(value)
176
177
178# 3. Lexer & Parser (Read) -----------------------------------------------
179
180
181def tokenize(source: str) -> list[str]:
182 """Split Scheme source code into tokens, ignoring comments and whitespace."""
183 tokens: list[str] = []
184 i = 0
185
186 while i < len(source):
187 char = source[i]
188
189 if char.isspace():
190 i += 1
191 continue
192
193 if char == ";":
194 newline = source.find("\n", i)
195 i = len(source) if newline == -1 else newline + 1
196 continue
197
198 if char in "()'":
199 tokens.append(char)
200 i += 1
201 continue
202
203 if char == '"':
204 start = i
205 i += 1
206 escaped = False
207 while i < len(source):
208 if escaped:
209 escaped = False
210 elif source[i] == "\\":
211 escaped = True
212 elif source[i] == '"':
213 i += 1
214 tokens.append(source[start:i])
215 break
216 i += 1
217 else:
218 raise IncompleteInput("unterminated string literal")
219 continue
220
221 start = i
222 while i < len(source) and not source[i].isspace() and source[i] not in "()'\";":
223 i += 1
224 tokens.append(source[start:i])
225
226 return tokens
227
228
229def atom(token: str) -> Any:
230 """Convert an atomic token into a boolean, String, number, or symbol (str)."""
231 if token == "#t":
232 return True
233 if token == "#f":
234 return False
235 if token.startswith('"'):
236 try:
237 return String(json.loads(token))
238 except json.JSONDecodeError as err:
239 raise SchemeSyntaxError(f"invalid string literal: {token}") from err
240 try:
241 return int(token)
242 except ValueError:
243 try:
244 return float(token)
245 except ValueError:
246 return token
247
248
249class Buffer:
250 """A simple token stream with lookahead for recursive-descent parsing."""
251
252 def __init__(self, tokens: Iterable[str]) -> None:
253 self.tokens = list(tokens)
254 self.index = 0
255
256 @property
257 def more(self) -> bool:
258 return self.index < len(self.tokens)
259
260 def current(self) -> str | None:
261 return self.tokens[self.index] if self.more else None
262
263 def pop_first(self) -> str:
264 if not self.more:
265 raise IncompleteInput("unexpected end of input")
266 token = self.tokens[self.index]
267 self.index += 1
268 return token
269
270
271def scheme_read(src: Buffer) -> Any:
272 """Read the next complete Scheme expression from token buffer src."""
273 if not src.more:
274 raise IncompleteInput("unexpected end of input")
275
276 token = src.pop_first()
277 if token == "(":
278 return read_tail(src)
279 if token == "'":
280 return Pair("quote", Pair(scheme_read(src), nil))
281 if token in (")", "."):
282 raise SchemeSyntaxError(f"unexpected token: {token}")
283 return atom(token)
284
285
286def read_tail(src: Buffer) -> Pair | _Nil:
287 """Read the remainder of a parenthesized list until the matching ')'."""
288 if not src.more:
289 raise IncompleteInput("unexpected end of input while reading list")
290
291 if src.current() == ")":
292 src.pop_first()
293 return nil
294
295 if src.current() == ".":
296 src.pop_first()
297 rest = scheme_read(src)
298 if not src.more:
299 raise IncompleteInput("unexpected end of input after '.'")
300 if src.pop_first() != ")":
301 raise SchemeSyntaxError("expected ')' after dotted tail")
302 return rest
303
304 first = scheme_read(src)
305 rest = read_tail(src)
306 return Pair(first, rest)
307
308
309def parse_program(source: str) -> list[Any]:
310 """Parse all top-level Scheme expressions from source string."""
311 src = Buffer(tokenize(source))
312 expressions: list[Any] = []
313 while src.more:
314 expressions.append(scheme_read(src))
315 return expressions
316
317
318# 4. Environments & Procedures -------------------------------------------
319
320
321class Env(dict[Symbol, Any]):
322 """An environment frame mapping symbols to values, chained to outer."""
323
324 def __init__(
325 self,
326 params: Iterable[Symbol] = (),
327 args: Iterable[Any] = (),
328 outer: Env | None = None,
329 ) -> None:
330 params_list = list(params)
331 args_list = list(args)
332 if len(params_list) != len(args_list):
333 raise SchemeError(
334 f"expected {len(params_list)} arguments, got {len(args_list)}"
335 )
336 super().__init__(zip(params_list, args_list))
337 self.outer = outer
338
339 def find(self, name: Symbol) -> Env:
340 """Return the innermost frame in which name is bound."""
341 if name in self:
342 return self
343 if self.outer is not None:
344 return self.outer.find(name)
345 raise SchemeError(f"unbound symbol: {name}")
346
347
348@dataclass
349class Procedure:
350 """A user-defined Scheme procedure (closure)."""
351
352 params: list[Symbol]
353 body: Pair
354 env: Env
355
356 def __call__(self, *args: Any) -> Any:
357 local_env = Env(self.params, args, self.env)
358 return eval_all(self.body, local_env)
359
360
361# 5. Built-in Procedures & Standard Environment --------------------------
362
363
364def require(condition: bool, message: str) -> None:
365 if not condition:
366 raise SchemeError(message)
367
368
369def is_true(value: Any) -> bool:
370 """In Scheme, only #f is false; everything else (including 0 and ()) is true."""
371 return value is not False
372
373
374def calc_add(*args: Any) -> Any:
375 return sum(args)
376
377
378def calc_sub(*args: Any) -> Any:
379 require(len(args) >= 1, "- requires at least 1 argument")
380 if len(args) == 1:
381 return -args[0]
382 return reduce(operator.sub, args[1:], args[0])
383
384
385def calc_mul(*args: Any) -> Any:
386 return reduce(operator.mul, args, 1)
387
388
389def calc_div(*args: Any) -> Any:
390 require(len(args) >= 1, "/ requires at least 1 argument")
391 try:
392 if len(args) == 1:
393 return 1 / args[0]
394 return reduce(operator.truediv, args[1:], args[0])
395 except ZeroDivisionError as err:
396 raise SchemeError("division by zero") from err
397
398
399def compare(name: str, op: Callable[[Any, Any], bool], *args: Any) -> bool:
400 require(len(args) >= 2, f"{name} requires at least 2 arguments")
401 return all(op(a, b) for a, b in zip(args, args[1:]))
402
403
404def builtin_car(pair: Any) -> Any:
405 require(isinstance(pair, Pair), "car requires a pair")
406 return pair.first
407
408
409def builtin_cdr(pair: Any) -> Any:
410 require(isinstance(pair, Pair), "cdr requires a pair")
411 return pair.second
412
413
414def builtin_append(*lists: Any) -> Pair | _Nil:
415 items: list[Any] = []
416 for lst in lists:
417 require(is_proper_list(lst), "append requires proper lists")
418 items.extend(lst)
419 return as_scheme_list(*items)
420
421
422def builtin_list_ref(lst: Any, index: int) -> Any:
423 require(isinstance(lst, Pair), "list-ref requires a non-empty list")
424 try:
425 return lst[index]
426 except IndexError as err:
427 raise SchemeError(str(err)) from err
428
429
430def builtin_display(value: Any) -> _Unspecified:
431 if isinstance(value, String):
432 print(str(value), end="")
433 else:
434 print(to_scheme(value), end="")
435 return UNSPECIFIED
436
437
438def builtin_newline() -> _Unspecified:
439 print()
440 return UNSPECIFIED
441
442
443def scheme_apply(procedure: Any, args: Pair | _Nil) -> Any:
444 """Apply a built-in function or user-defined Procedure to a Scheme list of args."""
445 require(callable(procedure), f"{to_scheme(procedure)} is not callable")
446 py_args = list(args)
447 try:
448 return procedure(*py_args)
449 except SchemeError:
450 raise
451 except (ArithmeticError, TypeError, ValueError) as err:
452 raise SchemeError(str(err)) from err
453
454
455def standard_env() -> Env:
456 """Create the default global environment with built-in procedures."""
457 env = Env()
458 env.update(
459 {
460 "+": calc_add,
461 "-": calc_sub,
462 "*": calc_mul,
463 "/": calc_div,
464 "abs": abs,
465 "max": max,
466 "min": min,
467 "round": round,
468 "sqrt": math.sqrt,
469 "expt": pow,
470 "quotient": lambda a, b: math.trunc(a / b),
471 "modulo": operator.mod,
472 "=": lambda *xs: compare("=", operator.eq, *xs),
473 "<": lambda *xs: compare("<", operator.lt, *xs),
474 "<=": lambda *xs: compare("<=", operator.le, *xs),
475 ">": lambda *xs: compare(">", operator.gt, *xs),
476 ">=": lambda *xs: compare(">=", operator.ge, *xs),
477 "not": lambda x: x is False,
478 "eq?": lambda a, b: a is b if isinstance(a, Pair) else a == b,
479 "equal?": operator.eq,
480 "number?": lambda x: isinstance(x, (int, float))
481 and not isinstance(x, bool),
482 "symbol?": is_symbol,
483 "string?": lambda x: isinstance(x, String),
484 "boolean?": lambda x: isinstance(x, bool),
485 "procedure?": callable,
486 "pair?": lambda x: isinstance(x, Pair),
487 "null?": lambda x: x is nil,
488 "list?": is_proper_list,
489 "cons": Pair,
490 "car": builtin_car,
491 "cdr": builtin_cdr,
492 "list": as_scheme_list,
493 "append": builtin_append,
494 "length": len,
495 "list-ref": builtin_list_ref,
496 "apply": lambda proc, args: scheme_apply(proc, args),
497 "map": lambda proc, lst: lst.map(
498 lambda x: scheme_apply(proc, Pair(x, nil))
499 ),
500 "filter": lambda pred, lst: as_scheme_list(
501 *[x for x in lst if is_true(scheme_apply(pred, Pair(x, nil)))]
502 ),
503 "display": builtin_display,
504 "newline": builtin_newline,
505 "pi": math.pi,
506 }
507 )
508 return env
509
510
511# 6. Evaluator & Special Forms (Eval) ------------------------------------
512
513
514def check_form(expr: Pair, min_len: int, max_len: int | None = None) -> None:
515 if not is_proper_list(expr):
516 raise SchemeSyntaxError(f"malformed expression: {to_scheme(expr)}")
517 length = len(expr)
518 if length < min_len or (max_len is not None and length > max_len):
519 raise SchemeSyntaxError(f"bad syntax in {to_scheme(expr)}")
520
521
522def check_params(params: Any) -> list[Symbol]:
523 require(is_proper_list(params), "parameter list must be a proper list")
524 result: list[Symbol] = []
525 for p in params:
526 require(is_symbol(p), f"invalid parameter name: {to_scheme(p)}")
527 require(p not in result, f"duplicate parameter name: {p}")
528 result.append(p)
529 return result
530
531
532def eval_all(expressions: Pair | _Nil, env: Env) -> Any:
533 """Evaluate a sequence of expressions in order and return the last value."""
534 result: Any = UNSPECIFIED
535 for expr in expressions:
536 result = scheme_eval(expr, env)
537 return result
538
539
540def scheme_eval(expr: Any, env: Env) -> Any:
541 """Evaluate a Scheme expression in environment env."""
542 # 1. Symbols are looked up in the environment
543 if is_symbol(expr):
544 return env.find(expr)[expr]
545
546 # 2. Self-evaluating atoms (numbers, booleans, String literals)
547 if not isinstance(expr, Pair):
548 if expr is nil:
549 raise SchemeSyntaxError("cannot evaluate an empty list ()")
550 return expr
551
552 check_form(expr, 1)
553 first = expr.first
554 rest = expr.second
555 form = first if is_symbol(first) else None
556
557 # 3. Special forms
558 if form == "quote":
559 check_form(expr, 2, 2)
560 return rest.first
561
562 if form == "if":
563 check_form(expr, 3, 4)
564 if is_true(scheme_eval(rest.first, env)):
565 return scheme_eval(rest.second.first, env)
566 if len(expr) == 4:
567 return scheme_eval(rest.second.second.first, env)
568 return UNSPECIFIED
569
570 if form == "define":
571 check_form(expr, 3)
572 target = rest.first
573 if is_symbol(target):
574 check_form(expr, 3, 3)
575 env[target] = scheme_eval(rest.second.first, env)
576 return UNSPECIFIED
577 if isinstance(target, Pair) and is_symbol(target.first):
578 name = target.first
579 params = check_params(target.second)
580 env[name] = Procedure(params, rest.second, env)
581 return UNSPECIFIED
582 raise SchemeSyntaxError(f"invalid define target: {to_scheme(target)}")
583
584 if form == "set!":
585 check_form(expr, 3, 3)
586 target = rest.first
587 require(is_symbol(target), "set! target must be a symbol")
588 env.find(target)[target] = scheme_eval(rest.second.first, env)
589 return UNSPECIFIED
590
591 if form == "lambda":
592 check_form(expr, 3)
593 params = check_params(rest.first)
594 return Procedure(params, rest.second, env)
595
596 if form == "begin":
597 return eval_all(rest, env)
598
599 if form == "let":
600 check_form(expr, 3)
601 bindings = rest.first
602 require(is_proper_list(bindings), "let bindings must be a list")
603 names: list[Symbol] = []
604 values: list[Any] = []
605 for binding in bindings:
606 require(
607 isinstance(binding, Pair) and is_proper_list(binding) and len(binding) == 2,
608 f"invalid let binding: {to_scheme(binding)}",
609 )
610 name = binding.first
611 require(is_symbol(name), "let binding name must be a symbol")
612 require(name not in names, f"duplicate let binding: {name}")
613 names.append(name)
614 values.append(scheme_eval(binding.second.first, env))
615 return eval_all(rest.second, Env(names, values, env))
616
617 if form == "and":
618 result: Any = True
619 for sub_expr in rest:
620 result = scheme_eval(sub_expr, env)
621 if not is_true(result):
622 return False
623 return result
624
625 if form == "or":
626 for sub_expr in rest:
627 result = scheme_eval(sub_expr, env)
628 if is_true(result):
629 return result
630 return False
631
632 if form == "cond":
633 for idx, clause in enumerate(rest):
634 require(
635 isinstance(clause, Pair) and is_proper_list(clause),
636 f"invalid cond clause: {to_scheme(clause)}",
637 )
638 is_else = is_symbol(clause.first) and clause.first == "else"
639 if is_else:
640 require(idx == len(rest) - 1, "else must be the last clause in cond")
641 test_val: Any = True
642 else:
643 test_val = scheme_eval(clause.first, env)
644 if is_true(test_val):
645 if clause.second is nil:
646 return test_val
647 return eval_all(clause.second, env)
648 return UNSPECIFIED
649
650 # 4. Ordinary procedure call: evaluate operator and all operands, then apply
651 operator_proc = scheme_eval(first, env)
652 operands = rest.map(lambda sub_expr: scheme_eval(sub_expr, env))
653 return scheme_apply(operator_proc, operands)
654
655
656# 7. REPL & File Execution -----------------------------------------------
657
658
659def evaluate(source: str, env: Env | None = None) -> tuple[list[Any], Env]:
660 """Parse and evaluate all expressions in source string."""
661 if env is None:
662 env = standard_env()
663 results = [scheme_eval(expr, env) for expr in parse_program(source)]
664 return results, env
665
666
667def repl(env: Env | None = None) -> None:
668 """Run an interactive Read-Eval-Print Loop."""
669 if env is None:
670 env = standard_env()
671 buffer_text = ""
672
673 while True:
674 try:
675 prompt = "scm> " if not buffer_text else "... "
676 buffer_text += input(prompt) + "\n"
677 try:
678 expressions = parse_program(buffer_text)
679 except IncompleteInput:
680 continue
681
682 for expr in expressions:
683 value = scheme_eval(expr, env)
684 if value is not UNSPECIFIED:
685 print(to_scheme(value))
686 buffer_text = ""
687 except SchemeError as err:
688 print(f"{type(err).__name__}: {err}")
689 buffer_text = ""
690 except (EOFError, KeyboardInterrupt):
691 print("\nbye")
692 return
693
694
695def run_file(filename: str, env: Env | None = None) -> Env:
696 if env is None:
697 env = standard_env()
698 source = Path(filename).read_text(encoding="utf-8")
699 for expr in parse_program(source):
700 scheme_eval(expr, env)
701 return env
702
703
704if __name__ == "__main__":
705 if len(sys.argv) > 2:
706 raise SystemExit(f"Usage: {sys.argv[0]} [file.scm]")
707 global_env = standard_env()
708 if len(sys.argv) == 2:
709 run_file(sys.argv[1], global_env)
710 else:
711 repl(global_env)

运行与测试

直接启动交互式 REPL：

bash
1python3 scheme.py

也可以将代码保存为 .scm 文件后执行：

bash
1python3 scheme.py example.scm

在 REPL 中可以测试递归函数、点对、列表与高阶函数：

scheme
1scm> (define (factorial n)
2... (if (= n 0)
3... 1
4... (* n (factorial (- n 1)))))
5scm> (factorial 10)
63628800
7
8scm> (cons 1 2)
9(1 . 2)
10scm> (cons 1 (cons 2 (cons 3 '())))
11(1 2 3)
12
13scm> (map (lambda (x) (* x x)) '(1 2 3 4 5))
14(1 4 9 16 25)
15scm> (filter (lambda (x) (> x 2)) '(1 2 3 4 5))
16(3 4 5)