Scheme解释器构建
- 本节我们将深入研究程序语言的解释器的构造，最终的目标是用python实现一个Scheme语言的解释器。
- python解释器在处理程序时会使用类似树递归的方式，逐层运行程序中的函数与表达式。从这个角度而言，解释器更像python程序的一本“说明书”，进而可以模块化并扩展。
基于Scheme语法的计算器
- 首先，我们从最基本的四则运算开始，构建一个基于Scheme语法的计算器。其基本示例如下：
> (+ 1 2 3 4) 10 > (+) 0 > (* 1 2 3 4) 24 > (*) 1 > (- 10 1 2 3) 4 > (- 3) -3 > (/ 15 12) 1.25 > (/ 30 5 2) 3 > (/ 10) 0.1 - 基于这个规则，我们使用python构建一个解释器程序，其可以接收一个表达式字符串并返回其表达式结果（如果表达式不完整则抛出异常）。
表达式树（Expression Trees）
- 对上述Scheme表达式的结构进行剖析，我们发现：它们包含的基本元素包括数字（整数、浮点数）和字符串（运算符）。
- 基于此调用的表达式本质是Scheme列表，其中第一个元素是运算符，后面的元素都是操作数。
- Scheme列表可以用Scheme的
Pair类型表示，但不是所有的Pair都是列表。因此，为了在python中构造这种列表，我们需要建立一个特殊的Pair类（其支持第二个及后续元素为空或列表）- 一种实现如下（源自scheme_reader）：
class Pair(object): """A pair has two instance attributes: first and second. For a Pair to be a well-formed list, second is either a well-formed list or nil. Some methods only apply to well-formed lists. >>> s = Pair(1, Pair(2, nil)) >>> s Pair(1, Pair(2, nil)) >>> print(s) (1 2) >>> len(s) 2 >>> s[1] 2 >>> print(s.map(lambda x: x+4)) (5 6) """ def __init__(self, first, second): self.first = first self.second = second def __repr__(self): return "Pair({0}, {1})".format(repr(self.first), repr(self.second)) def __str__(self): s = "(" + str(self.first) second = self.second while isinstance(second, Pair): s += " " + str(second.first) second = second.second if second is not nil: s += " . " + str(second) return s + ")" def __len__(self): n, second = 1, self.second while isinstance(second, Pair): n += 1 second = second.second if second is not nil: raise TypeError("length attempted on improper list") return n def __getitem__(self, k): if k < 0: raise IndexError("negative index into list") y = self for _ in range(k): if y.second is nil: raise IndexError("list index out of bounds") elif not isinstance(y.second, Pair): raise TypeError("ill-formed list") y = y.second return y.first def map(self, fn): """Return a Scheme list after mapping Python function FN to SELF.""" mapped = fn(self.first) if self.second is nil or isinstance(self.second, Pair): return Pair(mapped, self.second.map(fn)) else: raise TypeError("ill-formed list") - 另外，对于空表
nil，解释器选择先创立一个nil类，再通过名称覆盖创建唯一的空表对象：class nil(object): """The empty list""" def __repr__(self): return "nil" def __str__(self): return "()" def __len__(self): return 0 def __getitem__(self, k): if k < 0: raise IndexError("negative index into list") raise IndexError("list index out of bounds") def map(self, fn): return self nil = nil() # 规定nil类只有一个实例 - 上面定义的
Pair类中，__repr__方法对应python的原始字符串输出，__str__方法则对应Scheme的字符串输出；另外，求长度，求指定索引元素和Scheme的map方法也同样在类中实现。使用示例：
>>> s = Pair(1, Pair(2, nil))
>>> s
Pair(1, Pair(2, nil))
>>> print(s)
(1 2)
>>> len(s)
2
>>> s[1]
2
>>> print(s.map(lambda x: x+4))
(5 6)- 进而，我们可以通过嵌套
Pair对象实现Scheme表达式的一般表示，如：
>>> expr = Pair('+', Pair(Pair('*', Pair(3, Pair(4, nil))), Pair(5, nil)))
>>> print(expr)
(+ (* 3 4) 5)
>>> print(expr.second.first)
(* 3 4)
>>> expr.second.first.second.first
3- 现在已经有了Scheme表达式的列表表示法，接下来我们就要完成以下任务：将Scheme表达式转为嵌套
Pair列表（表达式树），再对表达式树进行求值。
表达式解析（Parsing Expressions）
- 对表达式的解析主要分为两个部分：词法分析（lexical analyzer）和句法分析（syntactic analyzer）。简单而言，就是将表达式先分解，再重组为表达式树。
- 词法分析：也称分词器（tokenizer），作用是将表达式字符串转换为token（最小语法单元）序列，具体实现如下：
import string
import sys
_SYMBOL_STARTS = set('!$%&*/:<=>?@^_~') | set(string.ascii_lowercase) # 合法开头符号表示
_SYMBOL_INNERS = _SYMBOL_STARTS | set(string.digits) | set('+-.') # 合法内部符号表示
_NUMERAL_STARTS = set(string.digits) | set('+-.') # 合法的数字开头
_WHITESPACE = set(' \t\n\r') # 空白字符（分隔token）
_SINGLE_CHAR_TOKENS = set("()'") # 单字符token定义
_TOKEN_END = _WHITESPACE | _SINGLE_CHAR_TOKENS # token结束符
DELIMITERS = _SINGLE_CHAR_TOKENS | {'.'} # 分隔符token
def valid_symbol(s):
"""检查字符串 s 是否是一个合法的 Scheme 符号。"""
if len(s) == 0 or s[0] not in _SYMBOL_STARTS:
return False
for c in s[1:]:
if c not in _SYMBOL_INNERS:
return False
return True
def next_candidate_token(line, k):
"""从字符串 line 的位置 k 开始，找到下一个可能的 token。
返回 (token, new_position)。"""
while k < len(line):
c = line[k]
if c == ';':
return None, len(line)
elif c in _WHITESPACE:
k += 1
elif c in _SINGLE_CHAR_TOKENS:
return c, k+1
elif c == '#': # Boolean values #t and #f
return line[k:k+2], min(k+2, len(line))
else:
j = k
while j < len(line) and line[j] not in _TOKEN_END:
j += 1
return line[k:j], min(j, len(line))
return None, len(line)
def tokenize_line(line):
"""把整行字符串分解成 token 列表。（除去注释和空白字符）"""
result = []
text, i = next_candidate_token(line, 0)
while text is not None:
if text in DELIMITERS:
result.append(text)
elif text == '+' or text == '-':
result.append(text)
elif text == '#t' or text.lower() == 'true':
result.append(True)
elif text == '#f' or text.lower() == 'false':
result.append(False)
elif text == 'nil':
result.append(text)
elif text[0] in _NUMERAL_STARTS:
try:
result.append(int(text))
except ValueError:
try:
result.append(float(text))
except ValueError:
raise ValueError("invalid numeral: {0}".format(text))
elif text[0] in _SYMBOL_STARTS and valid_symbol(text):
result.append(text)
else:
print("warning: invalid token: {0}".format(text), file=sys.stderr)
print(" ", line, file=sys.stderr)
print(" " * (i+3), "^", file=sys.stderr)
text, i = next_candidate_token(line, i)
return result
def tokenize_lines(input):
"""得到一个迭代器，迭代时会依次得到每一行的token列表。"""
return map(tokenize_line, input)使用示例：
>>> tokenize_line('(+ 1 (* 2.3 45))')
['(', '+', 1, '(', '*', 2.3, 45, ')', ')']- 句法分析：将词法分析得到的序列转为表达式树（也称为抽象语法树AST），其本质是树递归。
- 在进行转化时，需要考虑表达式跨越多行的情况（在本课程中使用
Buffer类解决，具体代码见buffer.py）。具体实现如下（未考虑点表达式与符号引用的情形）：
def scheme_read(src): """Read the next expression from src, a Buffer of tokens. >>> lines = ['(+ 1 ', '(+ 23 4)) ('] >>> src = Buffer(tokenize_lines(lines)) >>> print(scheme_read(src)) (+ 1 (+ 23 4)) """ if src.current() is None: raise EOFError val = src.pop() if val == 'nil': return nil elif val not in DELIMITERS: # ( ) ' . return val elif val == "(": return read_tail(src) else: raise SyntaxError("unexpected token: {0}".format(val)) def read_tail(src): """Return the remainder of a list in src, starting before an element or ). >>> read_tail(Buffer(tokenize_lines([')']))) nil >>> read_tail(Buffer(tokenize_lines(['2 3)']))) Pair(2, Pair(3, nil)) >>> read_tail(Buffer(tokenize_lines(['2 (3 4))']))) Pair(2, Pair(Pair(3, Pair(4, nil)), nil)) """ if src.current() is None: raise SyntaxError("unexpected end of file") if src.current() == ")": src.pop() return nil first = scheme_read(src) rest = read_tail(src) return Pair(first, rest) - 在进行转化时，需要考虑表达式跨越多行的情况（在本课程中使用
- 注意到程序在抛出异常时使用了
EOFError和SyntaxError，这可以极大提高解释器的可用性。
求值器（Evaluator）
- 我们一步步分解求值器的实现。核心的顶层函数是
calc_eval，负责接收表达式（列表）输入并返回其值：def calc_eval(exp): """Evaluate a Calculator expression. >>> calc_eval(as_scheme_list('+', 2, as_scheme_list('*', 4, 6))) 26 >>> calc_eval(as_scheme_list('+', 2, as_scheme_list('/', 40, 5))) 10 """ if type(exp) in (int, float): return simplify(exp) elif isinstance(exp, Pair): arguments = exp.second.map(calc_eval) return simplify(calc_apply(exp.first, arguments)) else: raise TypeError(str(exp) + ' is not a number or call expression')simplify将浮点整数转为整数）；否则（若表达式是Scheme列表），取第一个元素作为操作符，剩下的元素作为操作数（分别递归取值），进入calc_apply进行求值。 calc_apply函数实现如下：def calc_apply(operator, args): """Apply the named operator to a list of args. >>> calc_apply('+', as_scheme_list(1, 2, 3)) 6 >>> calc_apply('-', as_scheme_list(10, 1, 2, 3)) 4 >>> calc_apply('-', as_scheme_list(10)) -10 >>> calc_apply('*', nil) 1 >>> calc_apply('*', as_scheme_list(1, 2, 3, 4, 5)) 120 >>> calc_apply('/', as_scheme_list(40, 5)) 8.0 >>> calc_apply('/', as_scheme_list(10)) 0.1 """ if not isinstance(operator, str): raise TypeError(str(operator) + ' is not a symbol') if operator == '+': return reduce(add, args, 0) elif operator == '-': if len(args) == 0: raise TypeError(operator + ' requires at least 1 argument') elif len(args) == 1: return -args.first else: return reduce(sub, args.second, args.first) elif operator == '*': return reduce(mul, args, 1) elif operator == '/': if len(args) == 0: raise TypeError(operator + ' requires at least 1 argument') elif len(args) == 1: return 1/args.first else: return reduce(truediv, args.second, args.first) else: raise TypeError(operator + ' is an unknown operator')- 这里使用了另外两个函数：
reduce表示将操作符迭代作用于所有操作数上；as_scheme_list是测试函数，用于在python中快速构建Scheme表达式。
- 这里使用了另外两个函数：
读取-求值-打印循环（Read-eval-print loops，REPL）
- 读取 - 求值 - 打印循环是解释器交互的重要形式（如python解释器就提供了交互式环境）。下面是一个最基本的实现：
class InputReader(object):
"""An InputReader is an iterable that prompts the user for input."""
def __init__(self, prompt):
self.prompt = prompt
def __iter__(self):
while True:
yield input(self.prompt)
self.prompt = ' ' * len(self.prompt)
def buffer_input():
return Buffer(tokenize_lines(InputReader('> ')))
def read_eval_print_loop():
"""Run a read-eval-print loop for calculator."""
while True:
src = buffer_input()
while src.more_on_line:
expression = scheme_read(src)
print(calc_eval(expression))其效果如下：
> (* 1 2 3)
6
> (+)
0
> (+ 2 (/ 4 8))
2.5
> (+ 2 2) (* 3 3)
4
9
> (+ 1
(- 23)
(* 4 2.5))
-12- 不过我们还可以增加两个功能进行改进：在出现错误时抛出异常，与在用户主动输入中断信号（如Ctrl + C）或出现EOF（可输入Ctrl + Z）时中断循环。改动如下：
>>> def read_eval_print_loop():
"""Run a read-eval-print loop for calculator."""
while True:
try:
src = buffer_input()
while src.more_on_line:
expression = scheme_read(src)
print(calc_eval(expression))
except (SyntaxError, TypeError, ValueError, ZeroDivisionError) as err:
print(type(err).__name__ + ':', err)
except (KeyboardInterrupt, EOFError): # <Control>-D, etc.
print('Calculation completed.')
return执行效果：
> )
SyntaxError: unexpected token: )
> 2.3.4
ValueError: invalid numeral: 2.3.4
> +
TypeError: + is not a number or call expression
> (/ 5)
TypeError: / requires exactly 2 arguments
> (/ 1 0)
ZeroDivisionError: division by zero- 所以，不同语言的REPL除了解析函数、求值函数和try语句处理异常类型存在区别之外，其他结构都基本相同。
基于Scheme抽象的解释器
- 完整的Scheme解释器实现与之前的计算器结构基本相同：解析器（生成表达式）+求值器（利用求值函数解释）。主要的区别在于表达式的特殊形式、用户自定义函数以及环境帧的管理。
- 下面给出部分改动（完整的实现可见project，建议读者自行实现）：
- 求值部分：在原本的
calc_eval基础上增加了特殊类型/自定义函数的判别，并考虑了环境（作用域）：
>>> def scheme_eval(expr, env): """Evaluate Scheme expression expr in environment env.""" if scheme_symbolp(expr): return env[expr] elif scheme_atomp(expr): return expr first, rest = expr.first, expr.second if first == "lambda": return do_lambda_form(rest, env) elif first == "define": do_define_form(rest, env) return None else: procedure = scheme_eval(first, env) args = rest.map(lambda operand: scheme_eval(operand, env)) return scheme_apply(procedure, args, env)- 函数应用部分：在
calc_apply的基础上增强其通用性，具体分为两种类型：PrimitiveProcedure和LambdaProcedure。- 前者直接由python函数实现，不一定需要访问当前环境；而后者在使用时需要创建一个新的环境帧，再对其
body传入参数并使用scheme_eval求值。
- 前者直接由python函数实现，不一定需要访问当前环境；而后者在使用时需要创建一个新的环境帧，再对其
- 求值部分：在原本的
环境（帧）
- 在解释器中，环境帧主要通过创建
Frame类的实例实现，对于每个实例，其包含：- 一个保存名称及对应绑定的字典
bindings； - 一个父帧（全局帧的父帧为
None）； lookup方法：用于查找符号对应的值（从当前帧一层层向外查找）；define方法：将符号与值绑定，存入字典中。
- 一个保存名称及对应绑定的字典
- 具体实现同样见project。
补充：尾递归
- 在Scheme语言中，循环并不是通过
For或While表达式实现，而是使用了最基本的递归。 - 不过，普通的递归相比直接迭代会占用更大的空间。而对于部分递归函数而言，我们可以使用一种特殊的方法进行优化：尾递归（Tail Recursion）。
- 对于可以尾递归的函数，程序会在当前帧运算完并向下传递后，将当前帧释放，从而节省运行空间。
- 那么如何判断一个递归函数是否适用尾递归呢？首先，尾递归的定义是：函数的所有递归调用都出现在函数的末尾。示例（在Scheme中）：
lambda表达式中的最后一个子表达式；- 函数帧
if表达式中的最后一个子表达式（else条件表达式）。
- 一个具体的例子（斐波那契数列计算）：
(define (factorial n k)
(if (= n 0) k
(factorial (-n 1) (* k n))))其中尾表达式(factorial (-n 1) (* k n))只有递归调用，因此可以用尾递归优化。
- 当然，一些递归函数虽然无法直接使用尾递归，但可以通过一定的转换变为可以尾递归的函数。
数据作为程序（Data as Programs）
- 事实上，我们还可以从另一个角度审视Scheme解释器。如果我们将程序看作机器，那么解释器就会接受机器的描述作为输入，再通过配置模拟描述的机器，实现其功能。
- 具体而言，Scheme列表中的元素除了数字，变量之外，还可以是表达式，甚至程序：
> (list 'quotient 10 2) ; 构建一个列表('quotient 10 2)
(quotient 10 2)
> (eval (list 'quotient 10 2)) ; 评估列表的值
5在以上代码中，使用'将内置函数变为符号（防止作为变量传入列表），从而得到一个表达式元素，最终通过eval得到表达式的值。
- 另外，Scheme还有一个“准引用”符号
`，其功能与引用基本相同，但可以结合“取消引用”符号,对引用表达式内的子表达式取消引用。比如：
> (define b 4)
> `(a ,(+ b 1))
(a 5)利用这一特性，我们就能构造返回表达式的函数而避开计算表达式的值：
> (define (make-add-procedure n) `(lambda (d) (+ d ,n)))
> (make-add-procedure 2)
(lambda (d) (+ d 2))进而我们就能编写生成整段代码的代码。
- Scheme/python作为动态编程语言（与C、Java等静态语言相对）中，对执行过程中构建的表达式进行求值是一个常见而强大的功能。
- 本质上，解释器是连接程序语言和数据对象的桥梁。这便是Lisp/Scheme的哲学：程序即数据，数据即程序。
宏（Macros）
- 最后，我们再介绍Scheme的一大功能——宏定义。与先前的变量/过程定义不同，宏定义的对象是操作符本身（与
if,and,add同级）。我们可以利用这个功能对语言进行扩展。 - 具体示例如下：
> (define-macro (twice expr) (list 'begin expr expr)) > (twice (print 2)) 2 2define-macro表达式将twice定义为一个待求值的表达式（并将操作符命名为twice），从而在调用twice表达式时会按照其定义的规则代入表达式参数并求值。也就是说，宏定义表达式过程的输入和返回都是表达式。- 注：上面的定义等价于
> (define (twice expr) (list 'begin expr expr)) > (twice '(print 2)) 2 2
- 注：上面的定义等价于
- 我们以另一个宏定义的实现（python中的
trace）结束我们的Scheme之旅：
(define-macro (trace expr)
(define ((operator (car expr)))
`(begin
(define original ,operator)
(define ,operator
(lambda (n)
(print (list ',operator n))
(original n)))
(define result ,expr)
(define ,operator original)
result)))
(define (fact n)
(if (<= n 1)
1
(* n (fact (- n 1)))))
(trace (fact 5))
;; 输出:
;; (fact 5)
;; (fact 4)
;; (fact 3)
;; (fact 2)
;; (fact 1)
;; (fact 0)
;; 120