解释器：控制流与函数

4.1 条件判断语句（If-Then-Else）

为实现条件判断语句（if-then-else）的控制流，添加了一个新命令：

(if condition yes)
(if condition yes no)

if 命令与计算器章节中的 (? yes no) 运算符类似。不同之处在于，“else” 部分是可选的。因此，代码需要进行修改以处理这两种情况。

def pl_eval(env, node):
   ...
    # 条件判断
    if len(node) in (3, 4) and node[0] in ('?', 'if'):
        _, cond, yes, *no = node
        no = no[0] if no else ['val', None] # “else” 部分是可选的
        new_env = (dict(), env) # 新作用域
        if pl_eval(new_env, cond):
            return pl_eval(new_env, yes)
        else:
            return pl_eval(new_env, no)

请注意，在计算条件之前，我创建了一个新的作用域。这允许在条件中进行变量声明，例如：(if (var aaa bbb) (then use aaa here))。这只是一种语法糖。

4.2 循环

循环命令的语法：

(loop condition body)
(break)
(continue)

处理循环命令的代码与处理 if 命令的代码有一个共同点：它会转换为 Python 中的循环，就像 if 命令会转换为 Python 中的 if 语句一样。

def pl_eval(env, node):
   ...
    # 循环
    if node[0] == 'loop' and len(node) == 3:
        _, cond, body = node
        ret = None
        while True:
            new_env = (dict(), env)
            if not pl_eval(new_env, cond):
                break
            ret = pl_eval(new_env, body)
        return ret

我们还添加了 break 和 continue 命令。它们是通过（滥用）Python 异常来实现的。如果你不喜欢这种技巧，或者不能使用异常，也可以通过 pl_eval 的返回值来显式地传递这些命令。

def pl_eval(env, node):
   ...
    # 循环
    if node[0] == 'loop' and len(node) == 3:
        _, cond, body = node
        ret = None
        while True:
            new_env = (dict(), env)
            if not pl_eval(new_env, cond):
                break
            try:
                ret = pl_eval(new_env, body)
            except LoopBreak:
                break
            except LoopContinue:
                continue
        return ret
    # break 和 continue
    if node[0] == 'break' and len(node) == 1:
        raise LoopBreak
    if node[0] == 'continue' and len(node) == 1:
        raise LoopContinue
class LoopBreak(Exception):
    def __init__(self):
        super().__init__('`break` 出现在循环外')

class LoopContinue(Exception):
    def __init__(self):
        super().__init__('`continue` 出现在循环外')

4.3 函数

语法：

(def func-name (arg-names...) body)
(call func-name args...)

函数定义的代码并没有做什么特别复杂的事情。它只是进行一些合理性检查，并将函数名放入映射中。

def pl_eval(env, node):
   ...
    # 函数定义
    if node[0] == 'def' and len(node) == 4:
        _, name, args, body = node
        # 合理性检查
        for arg_name in args:
            if not isinstance(arg_name, str):
                raise ValueError('参数名错误')
        if len(args) != len(set(args)):
            raise ValueError('参数重复')
        # 将函数添加到作用域中
        dct, _ = env
        key = (name, len(args))
        if key in dct:
            raise ValueError('函数重复')
        dct[key] = (args, body, env)
        return

请注意，我在键中添加了参数的数量，这允许一种 “重载” 形式 —— 具有相同名称但参数数量不同的函数可以共存。这也区分了函数名和变量名。

现在来处理 call 命令。函数参数被视为新的变量。只需创建一个新的作用域，将参数放入其中，然后计算函数体。

def pl_eval(env, node):
   ...
    # 函数调用
    if node[0] == 'call' and len(node) >= 2:
        _, name, *args = node
        key = (name, len(args))
        fargs, fbody, fenv = name_loopup(env, key)[key]
        # 参数
        new_env = dict()
        for arg_name, arg_val in zip(fargs, args):
            new_env[arg_name] = pl_eval(env, arg_val)
        # 调用
        try:
            return pl_eval((new_env, fenv), fbody)
        except FuncReturn as ret:
            return ret.val

特别注意：父作用域不是调用者的作用域，而是函数定义时的作用域。（在定义函数时会保存该作用域）。

(return) 命令的处理方式与 (break) 或 (continue) 类似。

def pl_eval(env, node):
   ...
    # 返回
    if node[0] == 'return' and len(node) == 1:
        raise FuncReturn(None)
    if node[0] == 'return' and len(node) == 2:
        _, val = node
        raise FuncReturn(pl_eval(env, val))
class FuncReturn(Exception):
    def __init__(self, val):
        super().__init__('`return` 出现在函数外')
        self.val = val

4.4 完成

恭喜。我们已经为一门小型编程语言构建了一个解释器。

def test_eval():
    def f(s):
        return pl_eval(None, pl_parse_prog(s))
    assert f('''
        (def fib (n)
            (if (le n 0)
                (then 0)
                (else (+ n (call fib (- n 1))))))
        (call fib 5)
    ''') == 5 + 4 + 3 + 2 + 1
    assert f('''
        (def fib (n) (do
            (var r 0)
            (loop (gt n 0) (do
                (set r (+ r n))
                (set n (- n 1))
            ))
            (return r)
        ))
        (call fib 5)
    ''') == 5 + 4 + 3 + 2 + 1

我们的解释器并不比上一章中的计算器复杂多少。变量通过额外的状态来处理，控制流被转换为 Python 的控制流 —— 基本上仍然是简单的递归。

这个解释器在执行时仍然依赖于现有的语言。那么，我们如何将我们的语言编译成机器码，并在 CPU 上原生运行呢？这就是下一个挑战。